Viewing a single comment thread. View all comments

mfb- t1_j240p1l wrote

It's a combination of tables with a few entries and clever algorithms.

What calculators do is a bit more complicated, but here is an approach that can be done with pen and paper and some time. Let's say we want to find the square root of 40. We know (look up) that 36 is a square, namely 6^(2), so the square root of 40 will be somewhere close to that.

40/6 = 6.666...

6 is too small for the square root, but 6.666... must be too large, so let's take the average of the two, 6.3333:

40/6.3333 = 6.3161 - pretty close!

Let's take the average of 6.3333 and 6.3161, which is 6.3247:

40/6.3247 = 6.32441 - even closer. Doing that two more steps:

6.324555321991

6.324555320336758664214273

Digits in bold are correct, so we got 18 correct digits in just four steps (or 19 if we round).

More digits of the square root of 40 for comparison: 6.324555320336758663997787

153

squigs t1_j24ngkj wrote

Really surprising how quickly this converges! I'd have thought we'd get 2 binary digits per step, not 4ish decimal!

9

mfb- t1_j24rwja wrote

It's one of the methods that converge really quickly, you double the number of correct digits with each step (that statement is independent of the base, and applies once you start getting some correct digits).

7

FearlessFaa t1_j248t9v wrote

I state here two mathematical facts used in the answer:

  • for any positive numbers m and n, where m < n and m, n > 0, the following is true:
    • m < (m + n) / 2 < n,
      • where (m + n) / 2 is the average of numbers m and n
  • for any numbers x > 1, it is true that:
    • x < x * x = x^2,
      • where x^2 is the square of x
7

mfb- t1_j24bs0w wrote

x < x * x is only true for x>1, but that's not relevant here.

What we do need (for x>0 and y>0): if x < y then y/x > 1 or equivalently y^2 / x > y. Same for the other direction, if x > y then y^2 / x < y. Here y is the square root we are looking for. This inequality makes sure one of our numbers is always too small while the other one is too large, i.e. the square root is in between.

3

Psyese t1_j24evge wrote

So how much memory does the calculator need to store all the squares in a table?

1

mfb- t1_j24l46t wrote

As mentioned, a calculator will typically do it a bit differently. Usually numbers are stored in floating point format. 40 wouldn't be stored as "40", but as 1.01*2^5 where 1.01 is a binary number. 1.01*2^5 = 101000 in binary which is 32+8=40 in decimal.

The square root of a product of two numbers is the product of square roots: sqrt(a*b) = sqrt(a)*sqrt(b). To calculate the square root of 2^(n), we just need to divide n by 2: sqrt(2^(5)) = 2^(5/2) = 2^2 * sqrt(2). The calculator knows sqrt(2), so it only needs to calculate the square root of 1.01 (in binary), or more generally any number between 1.0 and 1.111... = 10 (i.e. 2 in decimal). The smallest and largest number only differ by a factor 2. You can make a few entries in a table to use as starting values, or just use the same value for all cases - it won't be that far off anyway. Do a few steps of the method I showed, multiply the result by the square root of 2 if needed (if the original exponent was odd), combine it with the integer powers of 2 (here 2^(2)) and you get the square root.

15

RSA0 t1_j24rosr wrote

You don't need a table of squares. This method works, even if you don't start with a square. You just need to start as close as possible to the square root.

Even some crude approximation, like "closest power of 10", is enough for the initial value.

3

thefancyyeller t1_j27tfm3 wrote

Since it's binary and every stay is "squared" can't they just shift it?

1

mfb- t1_j28frma wrote

> and every stay is "squared"

Huh?

Bit shifts multiply by powers of 2.

1