Life In 19x19

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.

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

emeraldemon wrote:...
(a+b)^2 = 2...

I think you're a pincushion.

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



Where could I find scans from this manga ?

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.

How I would solve it:

daniel_the_smith wrote: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.

Joaz Banbeck wrote:

emeraldemon wrote:...
(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?

Harleqin wrote:

daniel_the_smith wrote: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?

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.

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.

emeraldemon wrote:

Joaz Banbeck wrote:

emeraldemon wrote:...
(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.

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 wrote:... 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

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