# 13th root of a 200-digit number - Hewlett Packard

This is a discussion on 13th root of a 200-digit number - Hewlett Packard ; What is the first thing you do after reading this: http://afp.google.com/article/ALeqM5...HXyEi3K50b2zBQ The actual newspaper article also listed the 200-digit number in question, but it is of course much easier and faster to enter it in your beloved 49/50 as 2397207667966701^13. ...

# Thread: 13th root of a 200-digit number

1. ## 13th root of a 200-digit number

What is the first thing you do after reading this:

The actual newspaper article also listed the 200-digit number in
question, but it is of course much easier and faster to enter it in

Then try and calculate the 13th root, using 13 XROOT.
I canceled the routine after a few minutes (running at full speed on
my PC, that is)
It was obviously getting nowhere.
That's quite strange, because the following UserRPL routine gets it in
1.2 seconds, on a real 49G:

ZNROOT
\<<
\-> Z N
\<<
Z \->NUM N XROOT R\->I @ first approximation
DO @ N-R iteration
N 1 - DUP2 * UNROT * OVER * Z + SWAP N * IDIV2
UNTIL 0 SAME
END
\>>
\>>

It's just an implementation of Newton-Rhapson iteration, and for the
problem above, a single iteration yields the result.
Perhaps an idea for the next ROM version?

Cheers,

Werner Huysegoms

2. ## Re: 13th root of a 200-digit number

>
> The actual newspaper article also listed the 200-digit number in
> question, but it is of course much easier and faster to enter it in
> your beloved 49/50 as 2397207667966701^13.
>
> Then try and calculate the 13th root, using 13 XROOT.
> I canceled the routine after a few minutes (running at full speed on
> my PC, that is)
> It was obviously getting nowhere.
> That's quite strange, because the following UserRPL routine gets it in
> 1.2 seconds, on a real 49G:
>
> ZNROOT
> \<<
> \-> Z N
> \<<
> Z \->NUM N XROOT R\->I @ first approximation
> DO @ N-R iteration
> N 1 - DUP2 * UNROT * OVER * Z + SWAP N * IDIV2
> UNTIL 0 SAME
> END
> \>>
> \>>
>
> It's just an implementation of Newton-Rhapson iteration, and for the
> problem above, a single iteration yields the result.
> Perhaps an idea for the next ROM version?
>
> Cheers,
>
> Werner Huysegoms

He must try to factor, a lengthy process.
G.E.

3. ## Re: 13th root of a 200-digit number

On Tue, 20 Nov 2007 02:15:31 -0600, Werner Huysegoms wrote:

> ...just an implementation of Newton-Rhapson iteration...

The CAS is fundamentally designed to calculate "exact" results,
not "approximate" results (what if another original
exact argument has the same leading digits,
but then veers off from the value actually given,
in which case there is *no* correct integer answer?)

The very fact that it was also a "given" (to the human calculator)
that "this is an *exact* 13th power"
was probably very helpful to the human calculator,
although not utilized by Newton-Rhapson methods,
which would have delivered the same answer
even for different initial arguments,
for which the answer would not have been exact.

The human (or even a program) might even have worked this out
from right to left, for example!

I therefore don't consider it a fault that "exact 13th roots
of unlimited-length integers" (even via XROOT) is not a built-in
operation (nor even are exact square roots, for that matter),
and are left instead to be programmed, if desired, by the user.

Here is a very long thread on square roots alone,
which indicates that there is much more to it than may seem:

Other things which don't "just happen" without addressing something deeper:

"Just stop smoking/drinking/gambling..."
"Just say no."
"Just stop the killing."
"Just hold a free and fair election."
"Just secure our borders."
"Just let the business sector take care of it."
[and thousands more]

-[ ]-

4. ## Re: 13th root of a 200-digit number

Hi John, long time no see.

On Nov 21, 12:52 am, "John H Meyers" wrote:
> On Tue, 20 Nov 2007 02:15:31 -0600, Werner Huysegoms wrote:
> > ...just an implementation of Newton-Rhapson iteration...

>
> The CAS is fundamentally designed to calculate "exact" results,
> not "approximate" results (what if another original
> exact argument has the same leading digits,
> but then veers off from the value actually given,
> in which case there is *no* correct integer answer?)

I don't give approximate results.
The above program was just a quick way to get the answer when you know
the result exists;
also, in this case, the numerical approximation has already 11 correct
digits, so that a single NR step will give the result.
I have another, more involved version of the above program that will
stop the NR iteration when the integer result is the same as the
previous iteration. If the remainder is zero, we're done, if not, it
returns 'XROOT(N,Z)' just like the built-in XROOT would. It's not
foolproof yet, and I'm actually not sure whether it can be ;-).

>
> I therefore don't consider it a fault that "exact 13th roots
> of unlimited-length integers" (even via XROOT) is not a built-in
> operation (nor even are exact square roots, for that matter),
> and are left instead to be programmed, if desired, by the user.
>

But it *is* a built-in operation, it just takes too long to finish.
If an algorithm can be improved upon, why not change it?

> Here is a very long thread on square roots alone,
> which indicates that there is much more to it than may seem:http://groups.google.com/group/comp..../thread/5a8fb5...
>

? That thread is about the way the BCD sqrt is calculated, and those
are my posts in between ;-)
Moreover, I don't want to return an approximation of a sqrt of a large
number, but (just like XROOT does now, but a lot faster) return the
integer root if it exists, and 'XROOT(N,Z)' otherwise.

Cheers,
Werner

5. ## Re: 13th root of a 200-digit number

Hi

Do you think the guy can only calculate the 13th root (he said he
trained for that) or say he can do 12th root ?

Jean-Yves

6. ## Re: 13th root of a 200-digit number

On Nov 21, 8:31 am, JYA wrote:
> Hi
>
> Do you think the guy can only calculate the 13th root (he said he
> trained for that) or say he can do 12th root ?
>
> Jean-Yves

Hi Jean-Yves.
I think it's specifically the 13th root, because there do not appear
to be any 'tricks' or shortcuts you can use.
Cheers, Werner

7. ## Re: 13th root of a 200-digit number

>
> ZNROOT
> \<<
> \-> Z N
> \<<
> Z \->NUM N XROOT R\->I @ first approximation
> DO @ N-R iteration
> N 1 - DUP2 * UNROT * OVER * Z + SWAP N * IDIV2
> UNTIL 0 SAME
> END
> \>>
> \>>
>

The above program is actually not getting anywhere either ;-)
There's a typo, the '*' after DUP2 ought to be '^'

ZNROOT
\<<
\-> Z N
\<<
Z \->NUM N XROOT R\->I @ first approximation
DO @ N-R iteration
N 1 - DUP2 ^ UNROT * OVER * Z + SWAP N * IDIV2
UNTIL 0 SAME
END
\>>
\>>

Cheers,
Werner

8. ## Re: 13th root of a 200-digit number

On Tue, 20 Nov 2007 00:15:31 -0800 (PST), whuyse@gmail.com wrote:

>What is the first thing you do after reading this:
>

What are the chances that a random 200 digit number (integer, I suppose) will
be a perfect square?

9. ## Re: 13th root of a 200-digit number

On 2007-11-21 18:46:26 +1100, whuyse@gmail.com said:
> Hi Jean-Yves.
> I think it's specifically the 13th root, because there do not appear
> to be any 'tricks' or shortcuts you can use.
> Cheers, Werner

what a useful talent then if all you can calculate is the 13th root
I wonder how he pulls that up at parties ! !
--
They who would give up an essential liberty for temporary security,
deserve neither liberty or security (Benjamin Franklin)

10. ## Re: 13th root of a 200-digit number

On Tue, 20 Nov 2007 00:15:31 -0800 (PST), whuyse@gmail.com wrote:

>What is the first thing you do after reading this:
>

I don't think they selected a random 200 digit number, because the probability
of a random 200 digit number having a 13th root which is an integer is about
10E-185. I think they picked a random integer N such that
2030917620904734 < N < 2424462017082329 and then gave him the 13th power of that
integer.

Even the probability of a random 200 digit number being a perfect square is
vanishingly small, much less a perfect 13th power.

11. ## Re: 13th root of a 200-digit number

Be careful with 13th roots, Werner. You could be playing around with dangerous
powers!

See: http://www.13throot.com/accueilang.htm

12. ## Re: 13th root of a 200-digit number

On Nov 21, 11:54 am, Rodger Rosenbaum wrote:
> On Tue, 20 Nov 2007 00:15:31 -0800 (PST), whu...@gmail.com wrote:
> >What is the first thing you do after reading this:

>
> I don't think they selected a random 200 digit number, because the probability
> of a random 200 digit number having a 13th root which is an integer is about
> 10E-185. I think they picked a random integer N such that
> 2030917620904734 < N < 2424462017082329 and then gave him the 13th power of that
> integer.
>
> Even the probability of a random 200 digit number being a perfect square is
> vanishingly small, much less a perfect 13th power.

Don't trust a newspaper to get things even remotely right.. my
newspaper mentioned that 'even a computer could not do it in 72
seconds', ha.
Cheers, Werner
BTW that should be 2030917620904735 < N < 2424462017082329 ;-))

13. ## Re: 13th root of a 200-digit number

On 21 nov, 11:54, Rodger Rosenbaum wrote:
> ... I think they picked a random integer N such that
> 2030917620904734 < N < 2424462017082329 and then ...

The number in question is very very probably prime (I haven't even
checked).
No random here.
G.E.

14. ## Re: 13th root of a 200-digit number

On Nov 21, 7:52 am, gerard.evr...@free.fr wrote:
> On 21 nov, 11:54, Rodger Rosenbaum wrote:
>
> > ... I think they picked a random integer N such that
> > 2030917620904734 < N < 2424462017082329 and then ...

>
> The number in question is very very probably prime (I haven't even
> checked).
> No random here.
> G.E.

Nope:

\$ factor 2397207667966701
2397207667966701: 3 5381 55681 2666947

15. ## Re: 13th root of a 200-digit number

On 21 nov, 17:19, "dataj...@gmail.com" wrote:
> On Nov 21, 7:52 am, gerard.evr...@free.fr wrote:
>
> > On 21 nov, 11:54, Rodger Rosenbaum wrote:

>
> > > ... I think they picked a random integer N such that
> > > 2030917620904734 < N < 2424462017082329 and then ...

>
> > The number in question is very very probably prime (I haven't even
> > checked).
> > No random here.
> > G.E.

>
> Nope:
>
> \$ factor 2397207667966701
> 2397207667966701: 3 5381 55681 2666947

I understand now : the factorization of the target 200 digit number is
3^13 * 5381^13 * 55681^13 * 2666947^13
and when the machine has found the 3^13 factor, it has to loop up to
5381 to find 5381^13, then still has to loop to 55681 to find
55681^13, then still to loop to 2666947 because it cannot know that it
doesn't have to go up to the square root of the remaining term (in
that case sqrt(2666947^13) about 6*10^41 !).

This is a lot of loops !

On the other hand, the decomposition of 2397207667966701 is very easy
because it can stop looping when it reaches 55681. This is
2666947/55681 = about 48 times faster.

How long does it take to factor 2397207667966701 ?

Just wait 48 times longer and you can see the 13th root of
2397207667966701^13 on screen...

16. ## Re: 13th root of a 200-digit number

gerard.evrard@free.fr wrote:
> On 21 nov, 17:19, "dataj...@gmail.com" wrote:
>> On Nov 21, 7:52 am, gerard.evr...@free.fr wrote:
>>
>>> On 21 nov, 11:54, Rodger Rosenbaum wrote:
>>>> ... I think they picked a random integer N such that
>>>> 2030917620904734 < N < 2424462017082329 and then ...
>>> The number in question is very very probably prime (I haven't even
>>> checked).
>>> No random here.
>>> G.E.

>> Nope:
>>
>> \$ factor 2397207667966701
>> 2397207667966701: 3 5381 55681 2666947

>
> I understand now : the factorization of the target 200 digit number is
> 3^13 * 5381^13 * 55681^13 * 2666947^13
> and when the machine has found the 3^13 factor, it has to loop up to
> 5381 to find 5381^13, then still has to loop to 55681 to find
> 55681^13, then still to loop to 2666947 because it cannot know that it
> doesn't have to go up to the square root of the remaining term (in
> that case sqrt(2666947^13) about 6*10^41 !).
>
> This is a lot of loops !
>
> On the other hand, the decomposition of 2397207667966701 is very easy
> because it can stop looping when it reaches 55681. This is
> 2666947/55681 = about 48 times faster.
>
> How long does it take to factor 2397207667966701 ?

\$ time factor 2397207667966701
2397207667966701: 3 5381 55681 2666947

real 0m0.625s
user 0m0.046s
sys 0m0.015s

Cheers

Rich

> Just wait 48 times longer and you can see the 13th root of
> 2397207667966701^13 on screen...
>
>
>