Arithmetic problem from Tobaku Haouden Zero.

[Solomon]

I'm reading this manga called 'Tobaku Haouden Zero', which is very similar to Kaiji or the SAW movies. Anyways [spoilers from this point on], in one of the games the protagonist Zero has to face, he's managed to figure out that essentially he needs to determine the 9th and 10th decimal place of √2. He already knows up to the 8th decimal place (apparently due to some Japanese mnemonic). So given that he knows up to 1.41421356, what is the quickest/most efficient way for Zero to figure out the next two digits, 1.41421356xx? He has no calculator, just paper and pencil and 20 other people with him in the room worried about getting impaled by spears if Zero can't solve this problem in under 25 minutes. I'll post what Zero did later.

[emeraldemon]

Dunno if there's a more clever way, but here's what I'd do:

let a = 1.41421356
we want to find some b such that
(a+b)^2 = 2
a^2 + 2ab + b^2 = 2
2ab + b^2 = 2-a^2
b(2a + b) = 2 - a^2

At this point I would just use binary search on b, starting with 50e-9. Then I have 100 numbers to search, so I have to do at most log_2 (100) = 7 checks.
total arithmetic:
2 - a^2 and 2*a are precomputed, 2 multiplications
Each step then requires b*(2a + b) -> 1 add and 1 multiply

Total: 9 multiplications, 7 adds (and 7 compares).

I have no idea if this is optimal, but I'm pretty confident I could do 9 long multiplications in 25 minutes.

If the 20 people in the room are willing to help, we can break the interval into chunks to get it done even faster. i.e. if we break the interval into 20 regions of 5, each person only has to do 2 or 3 multiplications. Although realistically you'd be better off breaking people into small groups and having 1 person calculate, and 2 or 3 watch for miscalculations... so maybe 10 pairs, each assigned 10 numbers to cover.

[Joaz Banbeck]

...
(a+b)^2 = 2...

I think you're a pincushion.

[Tryphon]

The fatest is to know the following by heart : 1.414213562373, if I'm not mistaken

Emeraldemon idea seems fine. Since b^2 is of order 10^18, we should be able not to take it into account in the calcul and just solve 2ab = 2 - a^2.

I recall too that Newton's method leads to iterating : u_{n + 1} = 1/2 * (u_n - 2/u_n), which doubles the number of decimals each step. Starting from u_n = 1,41421356, we have at least 5 correct decimals. I didn't check because baby's whinning, but it's likely to be the same calcul than Emeraldemon's modified idea.

Where could I find scans from this manga ?

[daniel_the_smith]

I had dreams about trying to solve this last night using some bastardized version of the technique I skim-read when we had that thread on the soroban...

Is there a method for doing a square root like you do long division? If there is I never learned it.

[Sverre]

How I would solve it:

Binary search for two digits is about 7 steps (2**7 = 128)
Multiplication of two 10-digit numbers is ~200 operations.
In total ~1400 operations, I feel I could probably do that in 25 minutes.

Using the fact that we have 20 people (do we have pen and paper for everyone?), I would do a 20-ary search (or a 10-ary search with an extra backup for each multiplication), which would take only two steps. We should have enough time to double-check the answer too, I hope.

[Harleqin]

Is there a method for doing a square root like you do long division? If there is I never learned it.

Yes, there is. I have to look it up, though.

[emeraldemon]

...
(a+b)^2 = 2...

I think you're a pincushion.

hmm?

edit:
let a = 1.41421356
we want some 1.41421356xx such that
1.41421356xx = sqrt(2)
let b = xx (i.e. some small number)
a+b = sqrt(2)
square both sides:
(a+b)^2 = 2

did I go wrong somewhere?

[daniel_the_smith]

Is there a method for doing a square root like you do long division? If there is I never learned it.

Yes, there is. I have to look it up, though.

Hm, it seems to me that the current suggestion is equivalent: http://www.therthdimension.org/MathScie ... eroot2.htm

(that is, the current suggestion seems to just be an expansion of the "find the largest y such that..." step)

I will not be doing that in my head, that's for sure. Every additional digit requires multiple multiplications of a number one digit longer than the prior digit, which doesn't seem at all practical. I wonder how hard newton's method is to do by hand?

[daniel_the_smith]

I looked up Newton's method.

It seems one more iteration should give more than enough digits:

.5 * (1.41421356 + 2 / 1.41421356)

I'm highly confident I could solve that correctly in 25 minutes. Deriving it, maybe not.

[Cassandra]

We can apply an algorithm used for quick search in a sorted list.

xx can be between "00" and "99", which is 100 elements.
But to prevent a mistake with rounding the 11th digit, we have to consider yyy between "000" and "999", which is 1000 elements.

Divide 1000 by 2, and we get 500. The 500th element of the list is 499.

1,41421356499 ^ 2 is greater than 2.

So yyy must be in the lower part of the 500-element-list.
500 divided by 2 is 250, the 250th element is 249.

1,41421356249 ^ 2 is greater than 2.

Again, yyy must be in the lower part of the list.
250 divided by 2 is 125.

1,41421356124 ^ 2 is smaller than 2.

We choose the upper part of the remaining list.
(250 + 125) / 2 = 187.5.

1,41421356188 ^ 2 is smaller than 2.

We choose the upper part of the remaining list.
(250 + 188) / 2 = 219.

1,41421356219 ^ 2 is smaller than 2.

We choose the upper part of the remaining list.
(250 + 219) / 2 = 235.

1,41421356235 ^ 2 is smaller than 2.

We choose the upper part of the remaining list.
(250 + 235) / 2 = 242.5.

1,41421356243 ^ 2 is greater than 2.

We choose the lower part of the remaining list.
(243 + 235) / 2 = 239.

1,41421356239 ^ 2 is greater than 2.

We choose the lower part of the remaining list.
(243 + 239) / 2 = 237.

1,41421356237 ^ 2 is smaller than 2.

So we have found that yyy can be 237, or 238, or 239, but we can be sure that xx = 23.

+ + + + + + + + + + + + + +

Don't know if I would be able to do this in 25 minutes, but perhaps there is some sort of shortcut.

1,41421356249 ^2 is 2,0000000003

So we could dramatically reduce the size of the following lists, e.g. have the next try with 1,41421356233.

+ + + + + + + + + + + + + +

Or - if the size of the list in question is smaller than 21 * 5 = 105 - perhaps the 20 other people can help with doing the arithmetics in steps of 0,00000000005.

[Joaz Banbeck]

...
(a+b)^2 = 2...

I think you're a pincushion.

hmm?

edit:
let a = 1.41421356
we want some 1.41421356xx such that
1.41421356xx = sqrt(2)
let b = xx (i.e. some small number)
a+b = sqrt(2)
square both sides:
(a+b)^2 = 2

did I go wrong somewhere?

Nope. My misunderstanding.

[BaghwanB]

Is the 8th digit from the mnemonic rounded up? So instead of the 6th-10th digits being 356ab it could actually be 355yz where y>4.

Wouldn't that double your search space if you weren't sure about that 8th digit? I know it is only one more high/low operation but it rattled through my brain.

Bruce "1+1=3 for large values of 1" Young

[daniel_the_smith]

... 2 / 1.41421356 ...

Realized driving to work that that is not an easy division problem... Fortunately, Newton's method can solve that, too: http://en.wikipedia.org/wiki/Division_(digital)#Fast_division_methods

[Kirby]

I bet Araban's solution takes advantage of the 20 bystanders. There are 20 possible digits (10 per x).