Computing square roots

Let’s say you want to take the square root of a real number \(a\) without a computer. How would you do it? How do you think a computer does it?

The only way I know any computer performs square roots practically is via the following recurrence:

\(s_1=1; s_n=\displaystyle \frac{1}{2} \left ( s_{n-1} + \frac{a}{s_{n-1}} \right )\),

where

\(\sqrt{a}=\displaystyle \lim_{n\to\infty}s_n\).

The recurrence derives from Newton’s Method of finding roots, as applied to the function \(f(x)=x^2-a\). But that is not the point; the point is the recurrence and how fast it converges to its goal. Typically, roots found via Newton’s Method exhibit quadratic convergence; that is, the error in an iteration is the square of the error of the previous iteration. It turns out that the above recurrence has an exact solution, and from this solution we can closely examine the convergence toward the above limit.

The way to see this solution is to set \(s_n=\sqrt{a} \coth{\theta_n}\), where the hyperbolic cotangent is

\(\coth{x}=\displaystyle \frac{e^{x}+e^{-x}}{e^{x}-e^{-x}}\).

The hyperbolic cotangent satisfies a doubling formula:

\(\coth{2 x}=\displaystyle \frac{1}{2} \left ( \coth{x} + \frac{1}{\coth{x}} \right )\).

The above recurrence then takes the simplified form

\(\theta_{1}=\tanh^{-1}{\sqrt{a}}; \theta_{n}=2 \theta_{n-1}\).

The solution to the original recurrence then easily follows:

\(s_n=\sqrt{a} \coth{ \left ( 2^{n-1} \tanh^{-1}{\sqrt{a}} \right ) }\).

One slight complication: for \(a>1\), \(\tanh^{-1}{\sqrt{a}}\) is a complex number with imaginary part = \(\frac{\pi}{2}\). Because the recurrence involves a doubling of the argument, the imaginary part has no effect on the result. That said, it is more direct to write the result as

\(s_n=\sqrt{a} \coth{ \left ( 2^{n-1} \Re \left [ \tanh^{-1}{\sqrt{a}} \right ] \right ) }\),

where \(\Re \left [ z \right ]\) denotes the real part of \(z\).

On the surface, it seems silly to express this solution to the recurrence in terms of the limit that it approximates. That said, the goal in deriving this solution was to examine how it converges to the limit. Along these lines, consider the following approximation, valid for large arguments:

\(\coth{x} \approx 1+2 e^{-2 x}\).

The error at later stages of the recurrence is then about

\(\displaystyle \left | \frac{s_n}{\sqrt{a}} – 1 \right | \approx 2 \times 10^{- \left (\log_{10}{e} \right ) \left ( \Re \left [ \tanh^{-1}{\sqrt{a}} \right ] \right ) 2^{n}} \).

For each increment in \(n\), the error is the square of the previous error, as I mentioned above being a characteristic of root finding via Newton’s Method. The solution allows us to be even more specific. Because \(\log_{10}{e} \approx 0.4343\) and \(\Re \left [ \tanh^{-1}{\sqrt{a}} \right ] \approx 1\) for most values of \(a>1\), each iteration supplies slightly less than \(2^n\) decimal places of accuracy.

Note that this analysis only applies to square roots of real numbers. For complex square roots, the initial guess in Newton’s Method must be complex, and the solution of the recurrence is more complicated.

Is it cheating to use a symbolic math computer to do your homework?

Fascinating demonstration given by Conrad Wolfram of Wolfram Research at TEDx, concerning the question of whether or not one cheats by using Wolfram Alpha to do your integrals for you.

The short answer to the question is that there is cheating going on, but not in the way someone who asks this question would think. The gist is that, as Wolfram claims, about 80% of math education consists of hand computations: computing integrals, derivatives, limits, roots, matrix inverses, etc. But not only is this all incredibly boring, but it also ill-prepares students for the real mathematical challenges out there. Really, the challenge is to teach students how to translate real-world problems in business, engineering, etc., into a mathematical language. Once the pure computation problem is set up, then a machine like Wolfram Alpha can turn the crack and generate data. The remaining challenge is to figure out how to interpret the data, and such an interpretation does not lend itself to a black/white solution.

Another point that Wolfram makes is that calculus should be taught a lot earlier than it is now. When, he does not say, but he makes the case that there are concept in calculus, namely the limit, that a “3 or 4 year-old” could grasp. He points to a terrific visual example of using inscribed polygons to approximate \(\pi\).  The greater point is that math education in the US needs a radical reshaping, and that computers are crucial in this reshaping.  The cheating done, in the meantime, is not by the students, but to the students, because they are being told that the computational tools they will use int he real world to solve problems are viewed as verboten in school.

In my opinion, Wolfram has a number of terrific points and his demonstration is valuable and should be viewed by anyone with an interest in math education.  But ultimately, Wolfram’s proposals would create a generation of students with too much trust in the computer, and by extension the people who program the computer.  One must remember that Wolfram is in the business of providing computational engines, and the stock of his company rises if the people behind his company are seen as the gatekeepers to a mysterious technology.  It is not unlike the trend of making automobile engines more computerized and less able to be worked on by average people.  By saying that the messiness of computation is boring and turns off students, we increase the reliance of math professionals on the computer and leave out the crucial skill of checking the computer for errors.

I have had quite a bit of experience with this issue in my work at IBM.  In semiconductor lithography, one of the main challenges is to simulate the physical processes involved in imaging circuit patterns on a wafer.  The calculations involved in this simulation are extremely complex and very heavy-duty.  We did rely on software packages to do a lot of this, but most of the time, the models we built with these software packages led us astray.  Was it a problem with the data, or was the computer lying to us, or, even more subtly, was the computer telling us the truth but we were making false assumptions about that truth?  The problems in trying to answer these questions were severe: taking data on the few running machines we had was expensive and getting time was difficult.  The software vendors were always too busy to answer our difficult questions about the integrity of their computational models.  The only practical way to deal with this was for IBM to have someone who could devise simple tests that would reverse-engineer the engine’s algorithm and assess from where mistakes were coming.

That someone was invariably myself, as I had all the necessary background, both from my schooling and my work experience.  I knew how to look under the hood.  More importantly, I knew how to derive the equations that went under the hood.  And many of these equations weren’t simple expressions that could be typed into Wolfram Alpha.  Rather, such equations required careful geometrical reasoning and pattern matching that was difficult, if not impossible, with which to trust such a tool as Wolfram Alpha.  In fact, I found it best to be completely distrustful of the computer as I was building my test cases.  These test cases would be designed so as to be hand computable, yet nontrivial.  Once these test cases were designed and computed, then the diagnosing of problems could commence.

Furthermore, without someone to understand how to plumb the depths of how computations are done, we would not get users who can diagnose incorrect results at the chip level.  That’s right, recall Intel’s Pentium FDIV error.  Finding this error took a forensic approach to computation – an approach that none of us would have in Wolfram’s world, as none of us would deign to even think about so lowly an operation as division.  And, irony of all ironies, Wolfram’s flagship product, Mathematica, has not been without its own problems over the years – not just standard-issue software bugs, but incorrect algorithms.

As to the point Wolfram makes that calculus can be taught a lot earlier – making allusions to 3 or 4 year-olds.  I’m not so sure.  Yes, the basic calculus concept of the limit is easy to grasp, but beyond the most superficial level it is essentially a deus ex machina.  Further, applying those limits to sequences and series involves the culmination of everything a typical calculus student has learned.  Sloppy analytical techniques leads to an inability to solve problems, even if the calculus concepts are well understood.  I have a terrific example of this from my days as an undergraduate tutor in the Math Dept at UMass.  I used to sit in the calculus drop-in centers for students taking the business calc [Math 127/128 for those of you who know of which I speak].  Now, I admit, this was not the calculus that one with serious mathematical curiosity took, but still.  Anyway, at some point in time, the students were required to perform double integrations of polynomials over 2 variables, and come up with a number as an answer.  The drop-in center got real busy with folks who were simply perplexed.  A typical conversation would go like this:

  • Me: So, tell me, what’s troubling you?
  • Student: I can’t do these integrals!
  • Me: Well, why don’t you do this one in front of me, and let’s see what’s wrong.
  • Student: OK.  So first I do the integral over y…is that right?
  • Me: Yes.
  • Student: Now I do it over x.  is that right?
  • Me: Looks good.
  • Student: Now I plug in the limits and…it gives me a different answer than what the answer key tells me.
  • Me: that’s because you added wrong.  1/2 – 1/3 = 1/6, not what you wrote.
  • Student: huh?  I don’t understand?
  • Me: Do you know how I got 1/6?
  • Student: No.

So, what we learn here is that the student understood the mechanics of integration, but couldn’t add fractions.  How is such a student supposed to comprehend a result from Wolfram Alpha?

So, I disagree that the mechanics of computation are best left to the experts.  I do think that there is a place for learning the mechanics of a root solve, or an integration – in fact, many, many such operations – as a part of math education.  I do agree that computers should play a greater role in math education, and perhaps elements of calculus could be taught earlier.  But hand computation is essential if we are going to educate a class of people ready to question authority.

Bullies and genocide

I plead with you to read this piece by Shalom Auslander.  I am ashamed to have thought of this myself.  Then again, no I’m not…

Brian is a fat dumpy turd who is going to get his ass kicked one day. Not by me, because I’m almost 40, and he’s not yet eight. But he’s a bully, and he’s been bullying my son, who is not yet five. I look at Brian—almost half my height and damn near double my weight, his barely-fitting XL “Transformers” t-shirt covered with bits of cake and ice cream, his fat little legs already starting to splay out in the manner of the morbidly obese, the cursed beams of his insufficient structure already too weak to cope with the oversized load they are being asked to support, his hollow, heavy-lidded eyes blinking out at the world in the sort of dumb, mouth-breathing incomprehension you see in mall kids and SS men and Glenn Beck—and I think about the genocide books I’ve been reading. They all wonder why. They all seem to think there’s a reason, and that if they can identify that reason, these horrible crimes will never happen again. The reason, they say, is poverty. The reason is racism, the West, the East, religion, atheism, capitalism, communism. But it isn’t.

The reason is Brian.

There is no reason for Brian. I’d like there to be. But there isn’t. Brian just is. Brian happens. Is Brian going to lead Hutus to slaughter Tutsis? I don’t know. Perhaps he’s not that ambitious. But if Brian were a Hutu, Brian would hack a Tutsi, no question about it. Brian would hack a lot of Tutsis. Brian would be the Hutu in that news footage, dancing around the mangled corpse of a young Tutsi with his bloody machete raised triumphantly overhead. Only fatter. And eating a Twinkie.

“That fat little asshole,” my wife said.

“Who?” I asked.

“Brian.”

She had just come upstairs from tucking our son into bed, which was when he told her what had happened. Brian had been teasing him on the bus, poking him and trying to steal his GI Joe doll.

“That fat little asshole,” she said again.

“Okay,” I said, putting down The History of Torture and Execution from Early Civilization Through Medieval Times to the Present. “Just calm down.”

My wife is Middle Eastern; if you don’t stop the rock-throwing right away, pretty soon you’re shutting down East Jerusalem. I reminded her that our son has a vivid imagination, and that while something probably did happen, we don’t know for certain exactly what it was, and after all, this is Woodstock, it’s not like he was attacked by the Crips, and eventually, by the way, he is going to have to learn to fight his own battles.

“Okay,” she said. “You’re right.”

My son began to cry. I went downstairs, sat on the edge of his bed, and asked him what was wrong.

“I was having a bad dream.”

“What about, buddy?”

“About Brian.”

That fat little asshole, I thought.

“What about him, buddy?”

“We’re on the bus,” he said, “and he’s picking on me and stealing my toys and then the bus stops and it’s my turn to get off but he won’t let me and the bus leaves and I can never get home.”

That fat little asshole.

I wanted to tell him that he didn’t need to worry, that there was a man who lived a long time ago named Charles Darwin, and that Darwin figured out that we all evolved from monkeys and apes, and that some of us are more evolved, and some of us are less evolved, and some of us—the Brians of the world—have actually devolved somehow into something less than apes. But I heard my shrink in my head, telling me that all your children need to know is that you love them, and will always love them, and that’s all that matters. And so I told my son that I love him, and that I would always love him, and that was all that mattered. I may have mentioned something about the fact that if Brian ever touched him again, I would cut him up into tiny bits, stick them on skewers, put him on the grill until he was all cooked up, and then feed him to the dogs. And that I really, really love him.

My son laughed.

“Will you mash him up into peanut butter and put him on a sandwich?”

I laughed and said I would.

“Will you drop him off a building and drop a piano on his head.”

He’s been watching a lot of Bugs Bunny lately.

“Will you…”

“Okay, buddy, it’s time to get some sleep.”

“Okay. I love you, Dad.”

“I love you, buddy.”

I went upstairs.

“That fat little asshole,” I said to my wife.

I picked up my History of Torture and Execution, and forced myself again to find the humor in it. Because it seems for some things—like the seemingly-genetic, obviously-incurable bestiality of man toward his fellow man—laughter isn’t the best medicine.

It’s the only goddamn medicine.

Where Local Control Goes Awry, Cont’d

A few days ago, I posted a story about the E Ramapo, NY school board.  The Board has a majority Hasidim and has used their clout to replace the long-serving attorney to the Board with one 4X as expensive and for the seeming purpose of trying to transfer tax dollars meant for public schools to the special needs programs at the yeshivot that the Hasidic children attend.  The VP of the Board and leader of the meeting in which the attorney was voted in over howls of protest from the non-Hasidic community was one Aron Wieder, who spent the 20 Nov meeting looking sullen and annoyed that he had to deal with angry people as he virtually ignored them.

While I thought Mr. Wieder lacked class and basic manners, I do not fault the Hasidim for their actions.  They are only doing what is in their interest and exercising the fruits of majority rule and the political process.

Mr. Wieder seems to have seen what we did in his performance that night.  Here is a speech to address the polarizing issue of the lawyer before the community:

A few thoughts:

  • “Change we can believe in…”?  Huh?  I didn’t think the frum went so much for Obama.
  • He basically accuses the non-Hasidic board members who claimed that they were never invited to interview the new lawyer of lying.  Nice way of uniting the community.
  • No proof offered in that accusation, BTW.
  • “God Bless America”: the hooting and hollering when he says this were just creepy.  Who was in the audience here?

No matter anyway: Mr. Wieder has been offered a position as Administrative Assistant to Spring Valley’s [Democratic, non-Jewish] Mayor, and has taken it.  Good for him.  But I hope that the inclusion of the Hasidim in their larger community brings folks closer together.

Where local control goes awry

When we lived in Poughkeepsie and kept kosher, we would occasionally travel down to Monsey in Rockland County for shopping.  There is a strip mall in Monsey in which every shop is exclusively kosher; it was there where we could do our one-stop grocery shopping and get some kosher Chinese.  Such a mall can only be supported by a strong and orthodox Jewish community, which Monsey is certainly.  Monsey, NY, a hamlet of the town of Spring Valley and part of the E Ramapo school district, is one of a handful of upstate NY villages that have gone majority Hasidic over the years.  And, as the taxpayers of E Ramapo school district have discovered, such a situation brings with it a special clash of interests that seems to be upending a social contract that has bonded Americans of all backgrounds for decades.

The story that has touched off this observation has to do with a seemingly boring meeting of the E Ramapo school board on Nov 20.  However, this meeting, held at 12:40 AM while most taxpayers were sleeping, was designed to slip a very controversial move through with minimal fuss.  That move was the changing of the Board’s legal representation, from the local attorney who had represented the board for the past 33 years, to a new one.  The new one, it was revealed, not only would charge 4 times as much for an appearance at a meeting, but also had problems with the Attorney General.  And the leader of the Board, Aron Wieder, wanted the change to be confirmed then and there, with no consideration of a transition plan or any other sort of risk management.  And this new attorney would be confirmed no matter what that evening.  How is this possible?

It was possible because, out of 9 members, the Board has 6 Hasidim.  As a rule, the Hasidim [nominally called “ultra-orthodox” in the news – I find that moniker meaningless] do not send their children to the public schoold, but to private yeshivot.  They do, however, pay taxes.  And, to their dismay, they were seeing their school taxes rise even as the local school population was dropping.  So the Hasidim did what we in America applaud: they took action, used their numbers, and got a majority to the school board.  This of course is disastrous news to the people who actually use the public schools, now that a majority of the board only has an interest in minimizing their taxes.  Now, supporters of the Hasidic community point out that they have not been all about slashing taxes and have, for example, expanded the full-time kindergarten.  Further, they, like anybody else, have an interest in quality public schools.

But this latest dealing with the attorney has rightfully set off the anger and mistrust of the non-Hasidic taxpayers.  Why would the Hasidic members, who ostensibly only wish to control costs, abruptly switch legal counsel to one that is 4 times more expensive?  The answer, it was revealed, was even more disturbing.  The new counsel is also the counsel for the school district of Lawrence, NY, which is also controlled by Hasidim, and has successfully diverted public funds for the special needs programs at their yeshivot.  There was no consideration of any other attorney.  One non-Hasidic board member stated for the record that he never met or interviewed the new counsel: the whole concept of the attorney switch was done behind the backs of the non-Hasidic board members.

The meeting was recorded and put on Youtube; a short contentious part can be seen here:

[The entire meeting, which is about an hour, is split into 6 parts: 1, 2, 3, 4, 5, 6.  It is worth watching it to see the entire context.]

As awful as the actions of Mr. Wieder are, I cannot fault him nor the Hasidic community.  What is happening is purely legal, albeit procedurally improper.  But in the grand scheme of things, the Hasidim have it right.  They were unhappy with a situation, they used the political process and their numbers to make things how they wanted it.  And now they are using their power to divert their tax dollars into causes they want.  You and I may not like what happened at that meeting, nor do we like the way Mr. Wieder runs things.

What is insane is the way schools are funded and boards are run.  The problem is that Mr. Wieder and his 5 cronies on the board were driven to be there because of what they felt were unfair expropriations of his tax dollars.  And now he’s turned it around on his community.  There needs to be more oversight from the states on these boards so that arbitrary decisions like those taken by Mr. Wieder could not be possible.  Mr. Wieder, through his arrogance and a sense of entitlement, put his board in major legal risk, as the superintendent so clearly points out.

The story did not end there.  An interim attorney was hired because of all the mess that Mr. Wieder never thought through, and the decision to hire Mr. Wieder’s attorney is still pending.  But the problem remains. What do you do when the majority of your school board, who are backed by a majority of the voters who send their kids to private schools, has no interest in the school?  This will be an interesting story to follow.