My HP49G+ with 2.09 ROM does not factor (2^67-1)?????
Zeno
site, verison 2.09, and it still does not factor the integer (2^67-1).
It brings back the integer and does not bring back the factors.
The integer is 147573952589676412927 and the non-returned factors are
193707721 and 761838257287
Could someone else with the 2.09 ROM try it and see if it works for
them...just curious if mine is working properly when it does not factor
the number (2^67-1)
Wes
> I updated my early HP49G+ ROM to the latest version from the HP web
> site, verison 2.09, and it still does not factor the integer (2^67-1).
> It brings back the integer and does not bring back the factors.
Yeah, what's with that. And I'll tell you what else doesn't work. I
was planning on using FACTOR in a loop to find the next mersenne prime
number and claim the $100,000 prize
(http://www.eff.org/awards/coop.php), but that doesn't work either.
Just kidding of course, but seriously, I think you're expecting way too
much from a calculator. It took 91.86 seconds to factor that number
using Maxima on my 2.4 GHz computer. Considering that the 49g+ runs at
75 MHz, and that it's running an emulator on top of that, I can't see
it finding the factors of such a number within several hours.
However I do wish that FACTOR would somehow indicate whether it
determined that the number was definitely prime, or whether it gave up
after a certain amount of time. As it is, you're left wondering.
-wes
Veli-Pekka Nousiainen
Also note that prime numbers are searched using a method
that is fast, but does not guarantee to find ALL prime numbers
At certain point it will fail to detect a prime number
what it is - is not documented...
The good thing is that it is a far faster by a warp 10
in detecting prime numbers than an exhaustive search.
Steen Schmidt
> Just kidding of course, but seriously, I think you're expecting way
> too much from a calculator. It took 91.86 seconds to factor that
> number using Maxima on my 2.4 GHz computer. Considering that the
> 49g+ runs at 75 MHz, and that it's running an emulator on top of
> that, I can't see it finding the factors of such a number within
> several hours.
The TI89 HW2 factors this in 145 seconds.
> However I do wish that FACTOR would somehow indicate whether it
> determined that the number was definitely prime, or whether it gave up
> after a certain amount of time. As it is, you're left wondering.
That's what ISPRIME? is for. In this case it determines the number not
to be prime within 3 seconds.
Regards
Steen
Steen Schmidt
> I updated my early HP49G+ ROM to the latest version from the HP web
> site, verison 2.09, and it still does not factor the integer
> (2^67-1). It brings back the integer and does not bring back the
> factors.
Why should that have been changed for ROM 2.09? It's not a bug, just a
limitation of the algorithm used in your calculator.
Regards
Steen
Wes
> The TI89 HW2 factors this in 145 seconds.
It looks like I owe Zeno an apology for my sarcastic comment then.
In fact, EMU48 factors it in 13.2 seconds. My real 49g+ gives up after
102.8 seconds. Makes me wonder how long it would have taken if it
hadn't given up. Looking at the EMU48:real49g+ speed ratios for other
factors, it looks like somewhere around 175 seconds.
> It took 91.86 seconds to factor that number using Maxima on my 2.4 GHz computer.
Also makes me wonder what Maxima's factor routine is doing.
> Also note that prime numbers are searched using a method
> that is fast, but does not guarantee to find ALL prime numbers
> At certain point it will fail to detect a prime number
Perhaps Maxima is using method that is guaranteed to find all prime
numbers.
FWIW, a TI-92 (not +) also fails to factor it before it gives up. It
runs at 10 MHz while the 89 runs the same processor at 12 MHz.
Man, 2^67 just isn't as big as it used to be.
-wes
Steen Schmidt
> > It took 91.86 seconds to factor that number using Maxima on my 2.4
> > GHz computer.
>
> Also makes me wonder what Maxima's factor routine is doing.
It's probably using an algorithm better suited for smaller factors than
the ones in question here.
> FWIW, a TI-92 (not +) also fails to factor it before it gives up. It
> runs at 10 MHz while the 89 runs the same processor at 12 MHz.
The factor-algorithm on the TIs does not time out (give up) now -
'(2^48+59)*(2^49-81)' factors in 78 seconds on a 49G+ with ROM 1.23
while my TI89 (HW2, AMS 2.09) was still at it after more than 2 hours
(I stopped it then). Curiously, ROM 2.09 falls for the time-limit at
120 seconds leaving only a partial factorization on the stack. The
biggest factor therein also falls for the time-limit , this time at 109
seconds, so even step-wise factorization is impossible.
The above is proof that factoring algorithms can vary tremendeously
even between calculators, though like performance is always expected
(by some).
Well, pretty soon the TI will have to do a bit better than it is now,
since it'll have to compete with HPGCC ;-)
Regards
Steen
Zeno
<wjlte...@yahoo.com> wrote:
Mathematica 4.2 factors it instantly, I mean in a blink of an eye.
Those Wolfram dudes i guess know what they are doing ;)
Teddy Chiang
didn't indicate the time-out situation. Both V1.23 and V92
ROM for EMU48 could figure out the correct answer on PC
as the "authentic calculator speed" unchecked.
Ted
Steen Schmidt
> Mathematica 4.2 factors it instantly, I mean in a blink of an eye.
> Those Wolfram dudes i guess know what they are doing ;)
I can't get Mathematica 4.2 installed on my calc. How do I do that?
Cheers,
Steen
Steen Schmidt
> It seems the issue is caused by a time-out process. But 49g+
> didn't indicate the time-out situation.
As has been stated numerous times already. But I don't know why this is
expected to be different on this ROM compared with an older ROM?
Regards
Steen
Teddy Chiang
Steen Schmidt 寫道：
I don't know why you're so unhappy with my post. I've never complained
about any 49g+ ROM issue. Because most bugs are not important
for my use. In the post, I just would like to say that the "FACTOR"
algorithm should be no problem.
I didn't know there're already mamy pepole talked about the point of
timeout process. And why people are still argue about the algorithm
issue now?
John H Meyers
to be able either to suspend the use of a timeout
or to lengthen it, provided that the command
makes itself interruptible by testing the CANCEL key
now and then.
I don't quite fathom why any command limits itself
via a timeout that the user can not control at all --
what if, for example, the thought had come to
stop any numeric integration after 60 seconds?
That would have made more accurate integration impossible,
much to the chagrin of many users; as it is, the user
can terminate the procedure at any time via CANCEL,
so why not let the user decide when to give up,
instead of arbitrarily "rationing" an upper limit
to what they can ever achieve?
[r->] [OFF]
Raymond Del Tondo
slightly OT, but reminds me of a 'feature'
of the HP-48G built-in CHOOSE engine.
If you had an input list with *very* many elements,
say with a few hundred entries,
and did a hotkey search for the last element,
while the cursor was somewhere near the first element,
it could take a considerable amount of time
until the calc would have found the wanted entry.
Meanwhile it appeared as if the calc got stuck,
and I found myself more than once trying to cancel the search.
But the original hotkey search was not interruptable
from a certain point on!
However searching a list for an item is faster using my SpeedUI package,
but I included the 'cancel search' feature in the replacement browser
engines,
so the user can terminate the search at any time.
Regards
Raymond
"John H Meyers" <jhme...@nomail.invalid> schrieb im Newsbeitrag
news:op.teneo...@w2kjhm.ia.mum.edu...
Jean-Yves Avenard
> However searching a list for an item is faster using my SpeedUI package,
> but I included the 'cancel search' feature in the replacement browser
> engines,
> so the user can terminate the search at any time.
It's also very fast on the 49G :)
JY
Greg M.
Hmm, I am not sure if it is considered good form to respond to such an
old post, but I'll proceed anyway. Please let me know. :)
While reading the excellent "Programming in System RPL" (second
edition) by Euwardo M Kalinowski and Carsten Dominik, I came across the
following summary of an entry point by the name of ^BFactor:
"
Addr: 0CF006 Name: ^BFactor
Factors long integer. Brent-Pollard, with the assumption that trial
division has been done already. When a small factor is found SFactor is
called to get full short factorization. Since the factorization can
potentially take a very long time, an execution test is used to abort
factoring very long integers (limit is 60s for each composite). The
factors are sorted at exit.
"
By using Nosy, it appears that this execution test is done by comparing
a hex string against a call to SysTime which is made at the beginning
of the function. So, by simply altering the value contained in the HXS
object, one can increase the execution limit.
Further, it appears that ^BFactor is one of the routines which may be
called during a FACTOR run.
While a more advanced user would doubtless be able to recompile the
entire FACTOR function, to save full type checking & such, I have
contented myself with merely recompiling the ^BFactor function, which
seems to do at least a partial factorization of large numbers (It seems
to assume that "small" factors like 2,3,5, etc, have already been
factored out).
So, I used nosy & emacs to grab the ^BFactor function, and saved a copy
of it with the HXS object changed to the equivalent of 2 hrs, which
should be enough for all but the most demanding factorizations.
When this altered BFactor is executed with a ZINT of value 2^67-1 as
the argument, it does indeed return:
{ 193707721 761838257287 }
According to TEVAL, it took approx. 532 sec, or 8 min 52 sec to perform
the operation.
However, at this point, I'm not sure what the best way to go about
posting my actual program is. It's nowhere near worth cluttering up
hpcalc.org with, nor do I want to post a URL that will only be broken a
few years from now. The modifications were trivial enough that most
people here should be able to reproduce my work quite easily, but... If
someone wants it, send an email, and I'll do my best to get it to you.
Greg M.