Life In 19x19
http://prod.lifein19x19.com/

Arithmetic problem from Tobaku Haouden Zero.
http://prod.lifein19x19.com/viewtopic.php?f=8&t=4290		 Page 1 of 2
Author:  Solomon [ Tue Jul 19, 2011 7:30 pm ]
Post subject:  Arithmetic problem from Tobaku Haouden Zero.
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.

Image
Author:  emeraldemon [ Tue Jul 19, 2011 9:34 pm ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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.
Author:  Joaz Banbeck [ Tue Jul 19, 2011 10:56 pm ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
emeraldemon wrote:
...
(a+b)^2 = 2...


I think you're a pincushion. :lol:
Author:  Tryphon [ Tue Jul 19, 2011 11:54 pm ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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 ?
Author:  daniel_the_smith [ Wed Jul 20, 2011 5:33 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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.
Author:  Sverre [ Wed Jul 20, 2011 5:55 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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.
Author:  Harleqin [ Wed Jul 20, 2011 5:59 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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.
Author:  emeraldemon [ Wed Jul 20, 2011 6:09 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
Joaz Banbeck wrote:
emeraldemon wrote:
...
(a+b)^2 = 2...


I think you're a pincushion. :lol:



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?
Author:  daniel_the_smith [ Wed Jul 20, 2011 6:52 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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?
Author:  daniel_the_smith [ Wed Jul 20, 2011 7:11 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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. :)
Author:  Cassandra [ Wed Jul 20, 2011 7:25 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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.
Author:  Joaz Banbeck [ Wed Jul 20, 2011 7:49 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
emeraldemon wrote:
Joaz Banbeck wrote:
emeraldemon wrote:
...
(a+b)^2 = 2...


I think you're a pincushion. :lol:



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.
Author:  BaghwanB [ Wed Jul 20, 2011 8:39 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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
Author:  daniel_the_smith [ Wed Jul 20, 2011 8:45 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
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
Author:  Kirby [ Wed Jul 20, 2011 9:00 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
I bet Araban's solution takes advantage of the 20 bystanders. There are 20 possible digits (10 per x).
Author:  daniel_the_smith [ Wed Jul 20, 2011 9:23 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
Kirby wrote:
I bet Araban's solution takes advantage of the 20 bystanders. There are 20 possible digits (10 per x).


Maybe I'm too pessimistic, but given 20 random adults, I'd expect maybe 10 of them to be able to get a 10 digit multiplication problem correct in 25 minutes under that kind of pressure.
Author:  ChradH [ Wed Jul 20, 2011 9:24 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
This reminds me of an interpolation method I learned some 30 years ago :)
It gives one digit per iteration:

1.41421356 is too small (too short), and 1.41421357 is already too big,
so lets take them for lower bound 'L' and upper bound 'U', respectively.

Calculate L^2 and U^2 and see where our goal 2 lies in between:

Let x = (2 - L^2) / (U^2 - L^2) = 0.237... for values above.
Take first digit after the decimal point as the next digit of the root: 1.414213562 and repeat.

Next iteration gives 1.4142135623.

That's two (long) multiplications and one (shorter) division per iteration. As we need only the first digit of x, it might even be possible to break the multiplications off early when they have reached enough significant digits.

In any case this should be possible with pencil and paper in 25 minutes. I used a calculator, of course :)
A really cool solution would use those 20 people around :lol:
Author:  Cassandra [ Wed Jul 20, 2011 9:29 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
Kirby wrote:
I bet Araban's solution takes advantage of the 20 bystanders. There are 20 possible digits (10 per x).

If there are enough pencils and paper, parallel processing might be possible.

There are 20 helpers, so let them calculate the squares with

xx = 00, 05, 10, ... , 95.

After the first run, the hero will find that 20 gives a result below 2, 25 a result above.

For the second run, the hero can let his helpers calculate in steps of .4, i. e.
20.4, 20.8, 21.2, ..., with the result that 23.6 is below and 24.0 is above 2.

The third, and decisive, run is the one for the hero, who calculates 23.9, with a result above 2.

So he can be sure that xx is 23.
Author:  BobC [ Wed Jul 20, 2011 10:54 am ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
I think you can bastardise Taylors theorem for this.
Take given: 1.41421356

1.41421356 - square it..
then turn the 56 into 57 - square it ( with one f the helpers)
then turn 56 into 565 - square it..
compare answers to 2 then interpolate and repeat with increasing precision...



it's like playing the "hi lo guess a number game". Should get it out in about 7 squares..
Author:  hyperpape [ Wed Jul 20, 2011 5:59 pm ]
Post subject:  Re: Arithmetic problem from Tobaku Haouden Zero.
This could be personal preference, but it feels easier to use the formula for square of sums, then subtract and do division, using a lot of "safe" approximations.

[1] (a + b)^2 = a^2 + 2ab + b^2.

[2] a = 1.41421356

[3] a ^ 2 = 1.99999999328

[4] 2 - a ^ 2 = 67.2... * 10 ^-9 (as far as the calculation is concerned, you can forget the -9).

[5] 67.2 / 2a ≈ 23

[6] b = 2.3 * 10^-9

=========

At [3], the b^2 term is extremely small. Unless 2 - a^2 looks wrong, you can ignore it.

You can do [5] with all the digits of the 67.2... term, as well as all the digits of a. But you're almost certainly not going to need them all. I'd start with 67.2 / 1.41 and see whether I might need to backtrack.
Page 1 of 2 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/