jpser@cup.portal.com (John Paul Serafin) (06/17/91)
I have stumbled across several integers which are factored by the ultimate
prime factor routines for the HP48 by Klaus Kalb and Jurjen Bos much
faster than Mathematica 1.2 running on a 25MHz 486. There were also
some integers which took 9 to 15 seconds on both machines. Because i/o
is so slow on the HP48, Mathematica is much faster on easy to factor
integers, but the 48 is so fast, it really doesn't matter. There are
many things which Mathematica can do and the HP48 can not, and in general
Mathematica is much faster. Nonetheless, I think these results say
some things about both the HP48 and Mathematica. (The "no math coprocessor
required" version of Mathematica was used, but I doubt that floating point
numbers are involved). I found these integers several weeks ago, but it
looks like I won't have time to do a good job of studying or documenting
any time soon. So, here are some of my results.
----------------------------------------------------------------------------
Number HP48 time Mathematica time (MSDOS 80486)
4,611,686,018,427,387,903
= 2^62 - 1 508 sec After more than 8 hours and
less than 20 hours, Mathematica
ran out of memory. (5M extended,
8M RAM swap disk. This case
was rerun with 12M extended
memory and 60M free space on a
fixed disk as swap space.
After nearly two days, the
problem was still running. The
run was aborted and MaxMemory
Used returned 43,761,628. The
HP48 had less than 6000 bytes
free at the start of the run.
128,573,131,101,428,317
= 573,259,391 * 241 sec After more than 8 hours, etc.
224,284,387 This was before trying hard
= 30,000,000th prime * swap and 12M main memory.
12,345,678th prime
50,303,624,411,148,161 151 sec "
= 224,284,387 *
224,285,003
5,260,991,541,853,343 45 sec I killed this one, too. Not
= 224,284,387 * sure when, but much longer
23,456,789 than 45 seconds.
The last is smallest number I have found so far that sends Mathematica out
to lunch. The largest number the HP48 can factor with the Kalb/Bos routine
is 2^64 -1.
Mathematica documentation states that Mathematica will factor a number
with fewer than 25 digits almost immediately (page 84 of the second
edition, page 554 says integers less than 20 digits should give no
problem.
I would be interested in knowing how Mathematica does with the above
numbers on other computers, perhaps with more memory, what the smallest
"pathological" integer for Mathematica is, and whether there are any
integers that take Mathematica more than 5 minutes and less than an hour.
John Serafin
jpser@cup.portal.compmontgom@euphemia.math.ucla.edu (Peter Montgomery) (06/17/91)
In article <43391@cup.portal.com> jpser@cup.portal.com (John Paul Serafin) writes: >I have stumbled across several integers which are factored by the ultimate >prime factor routines for the HP48 by Klaus Kalb and Jurjen Bos much >faster than Mathematica 1.2 running on a 25MHz 486. The second entry on the list has a typo, according to the factorization given >128,573,131,101,428,317 ^ 2 On a SUN 4/260, Maple V completes all four in 25 seconds: |\^/| MAPLE V ._|\| |/|_. Copyright (c) 1981-1990 by the University of Waterloo. \ MAPLE / All rights reserved. MAPLE is a registered trademark of <____ ____> Waterloo Maple Software. | Type ? for help. > # HP 508 seconds (2^62 - 1) > ifactor(4611686018427387903); (3) (2147483647) (715827883) # HP 241 seconds (1428317 changed to 2428317) > ifactor(128573131102428317); bytes used=1000072, alloc=655240, time=6.483 bytes used=2000192, alloc=851812, time=11.616 bytes used=3000336, alloc=917336, time=17.366 (573259391) (224284387) # 573259391 * 224284387 ; # HP 151 seconds > ifactor(50303624411148161); (224285003) (224284387) # 224284387 * 224,285,003 # HP 45 seconds > ifactor(5260991541853343); (23456789) (224284387) # 224284387 * 23456789 > ;quit bytes used=3824236, alloc=917336, time=25.033 On the same machine, my own factor program takes 0.15 second to get 3 * 715827883 * 2147483647 using P-1, 0.61 second to get 224284387 * 573259391 using Pollard Rho, 0.60 second to get 224284387 * 224285003 using Pollard Rho, 0.61 second to get 224284387 * 23456789 using Pollard Rho, for a total of two seconds. The P-1 method may seem not to work for the first example since 2^62-1 = 3pq where p = 715827883 = 1 + 2 * 3 * 7 * 11 * 31 * 151 * 331 q = 2147483647 = 1 + 2 * 3 * 3 * 7 * 11 * 31 * 151 * 331 and so p-1 and q-1 have the same largest prime factor. To overcome this, after finding the factor 3 by trial division, select a base a and compute a' = a^(pq-1) mod pq, using a' as the initial base for P-1. In this case, unless a is a cube mod q, we will achieve a' == 1 mod p but a' !== 1 mod q, and the first GCD will uncover our divisor p (after backtracking). This technique also works when trying to factor a prime power p^k using P-1 (a topic discussed in sci.math.symbolic recently), since the initial base a^(p^k - 1) mod p^k will be congruent to 1 mod p. However, it does not necessarily work for p^2 q. -- Peter L. Montgomery pmontgom@MATH.UCLA.EDU Department of Mathematics, UCLA, Los Angeles, CA 90024-1555 If I spent as much time on my dissertation as I do reading news, I'd graduate.
doug@wri.com (Doug Stein) (06/18/91)
I just tried these using Mathematica 2.0 (beta4) and got the following:
Sparc 1+:
FactorInteger[4611686018427387903]//Timing
{28.1 Second, {{3, 1}, {715827883, 1}, {2147483647, 1}}}
FactorInteger[128573131102428317]//Timing
{78.1667 Second, {{224284387, 1}, {573259391, 1}}}
FactorInteger[50303624411148161]//Timing
{77.25 Second, {{224284387, 1}, {224285003, 1}}}
FactorInteger[5260991541853343]//Timing
{66.0833 Second, {{23456789, 1}, {224284387, 1}}}
Mac IIfx
FactorInteger[4611686018427387903]//Timing
{40.2833 Second, {{3, 1}, {715827883, 1}, {2147483647, 1}}}
FactorInteger[128573131102428317]//Timing
{177.867 Second, {{224284387, 1}, {573259391, 1}}}
FactorInteger[50303624411148161]//Timing
{138.667 Second, {{224284387, 1}, {224285003, 1}}}
FactorInteger[5260991541853343]//Timing
{100.417 Second, {{23456789, 1}, {224284387, 1}}}
Doug Stein
Wolfram Research, Inc.
doug@wri.comknighten@Encore.com (Robert L. Knighten) (06/18/91)
In article <1991Jun17.182703.28007@wri.com> doug@wri.com (Doug Stein) writes:
Path: encore!bu.edu!snorkelwacker.mit.edu!world!uunet!wri!doug
From: doug@wri.com (Doug Stein)
Newsgroups: comp.sys.handhelds,sci.math.symbolic
Date: 17 Jun 91 18:27:03 GMT
References: <43391@cup.portal.com>
Organization: Wolfram Research, Inc.
Lines: 33
Xref: encore comp.sys.handhelds:9408 sci.math.symbolic:2603
I just tried these using Mathematica 2.0 (beta4) and got the following:
Sparc 1+:
FactorInteger[4611686018427387903]//Timing
{28.1 Second, {{3, 1}, {715827883, 1}, {2147483647, 1}}}
Mac IIfx
FactorInteger[4611686018427387903]//Timing
{40.2833 Second, {{3, 1}, {715827883, 1}, {2147483647, 1}}}
Doug Stein
Wolfram Research, Inc.
doug@wri.com
Oh, the power of a good algorithm. I just ran that through the MPQS (Multiple
Polynomial Quadratic Sieve) program that is distributed with the UBASIC
program and on a random 16 MHz 386SX machine it took 5 seconds! Longer to
type in than to factor.
--
--
Bob Knighten
Encore Computer Corp., 257 Cedar Hill Street, Marlborough, MA 01752
Internet: knighten@encore.com (508) 460-0500 ext. 2626
uucp: encore!knighten (617) 926-0902jpser@cup.portal.com (John Paul Serafin) (06/20/91)
Someone at Rice University asked me for a list of ftp sites to find the ASC utilities for the HP48 handheld calculator, which are needed to install the prime factor program from Jurgen Bos. I accidentally deleted his email before preparing this reply. To mitigate the bandwidth usage, I would like to take this opportunity to apologize for the typo in one of the integers in my original post. This is from an old FAQ. I would try the hp stuff first, then the wuarchive hpcvaaz.cv.hp.com 15.255.72.15 pub hpcvbbs.cv.hp.com 15.224.72.16 pub (readme) wuarchive.wustl.edu 128.252.135.4 /systems/hp48sx funic.funet.fi 128.214.6.100 pub/misc/hp48sx pub/misc/hp28s gmuvax2.gmu.edu 129.174.1.8 new/hp48sx I am also glad to see that when Mathematica 2.0 finally comes out it will no longer require days (if ever?) to factor the integers in question. It is still interesting to note that Mma 2.0 on multi-thousand dollar workstations still won't be much faster that a $250 pocket calculator, and for at least one integer Mma will still be slower. John Serafin jpser@cup.portal.com