[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#59636: prime [ factor ] utility very slow in factoring the square of
From: |
Jason C. Kwan |
Subject: |
bug#59636: prime [ factor ] utility very slow in factoring the square of a prime |
Date: |
Sun, 27 Nov 2022 14:48:16 +0000 (UTC) |
The test case is
49,456,902,806,087,647,575,555,655,201
a prime that is approx. 95.3-bits in size, plus the direct squaring of it,
ascalculated by gnu-bc
(see full text below for host system info, versioning details, and
command line statements used to perform this test.
xargs used is macOS 12.6 built-in one instead of GNU one)
The base prime has a hex representation is
0x 9FCD CA89 5696 76C0 0B03 4621
The issue being that while it took the [ factor ] utility just shy of 4.8ms to
complete its primality checks, and confirmed the first input is indeed prime,
attempting to factor the direct squaring of the same prime resultedin the task
being timed out after 1200 seconds, or 20 minutes.
Perhaps there is an opportunity to optimize it by
- performing a quick square/square-root check for large inputs
(e.g. >= 2^127, per "info factor")
before routing it to what "info factor" refers to as "the slower algorithm" ?
Maybe also add one more cube/cube-root quick check if the relative cost to
system resources isn't particularly material ?
RegardsJason
% uname -mrsv
Darwin 21.6.0 Darwin Kernel Version 21.6.0: Mon Aug 22 20:19:52 PDT
2022;
root:xnu- 8020.140.49~2/RELEASE_ARM64_T6000 arm64
% gdate gfactor --version bc --version
Sun Nov 27 03:34:47 EST 2022
---------------------------------------------
factor (GNU coreutils) 9.1Copyright (C) 2022 Free Software Foundation,
Inc.License GPLv3+: GNU GPL version 3 or later
<https://gnu.org/licenses/gpl.html>.This is free software: you are free to
change and redistribute it.There is NO WARRANTY, to the extent permitted by law.
---------------------------------------------
Written by Paul Rubin, Torbjörn Granlund, and Niels Möller.bc 1.06Copyright
1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
---------------------------------------------
echo ' x = 49456902806087647575555655201 ; x^1 ; x^2 ; ' | bc
| xargs -t -n 1 -P 2 timeout
--foreground 1200 gfactor |
awk ' function ep16(__,_,___) { return substr("", (___ = RS) *
(RS = "\n") * \ ( (__ = " gdate +\"%s%6N\" ") | getline _),
close( __) ^ (RS = ___))_ }
function timer(_,__) { return \ +_ < (__= ep16())^(_<_) \ ?
__\ : (__-_) /\ ( ( (_+=_^=_<_)+_*_*_)^(_ +_+ _)*\ (
_++^!++_ + _^-(_ +_+--_) ) ) } BEGIN { __ = timer(_ = _<_) OFMT =
"%.25g" CONVFMT = "%.250g" _^=_ } ($++NF = sprintf("%.13f",
timer(__)))^!_ +\ ($++NF = log( $_ ) / log(_+_))^!_'
---------------------------------------------
timeout --foreground 1200 gfactor 49456902806087647575555655201timeout
--foreground 1200 gfactor
2445985235170800228886882843536511572299116327852398350401
49456902806087647575555655201: 49456902806087647575555655201 0.0047909999999
95.320158551927676171544590033590793609619140625
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- bug#59636: prime [ factor ] utility very slow in factoring the square of a prime,
Jason C. Kwan <=