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

+ Reply to Thread
Results 1 to 16 of 16

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

    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

    > 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.
    >
    > 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:
    http://groups.google.com/group/comp....ea01cb2f?tvc=1

    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:
    >http://afp.google.com/article/ALeqM5...HXyEi3K50b2zBQ
    >

    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:
    >http://afp.google.com/article/ALeqM5...HXyEi3K50b2zBQ
    >

    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:
    > >http://afp.google.com/article/ALeqM5...HXyEi3K50b2zBQ

    >
    > 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

    Not that long, and my system is busy with other tasks (like downloading FC8)

    Cheers

    Rich

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


+ Reply to Thread