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, as
calculated 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 resulted
in 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 ?
Regards
Jason
% 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.1
Copyright (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.06
Copyright 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(_ = _<_)
CONVFMT = "%.250g"
_^=_
} ($++NF = sprintf("%.13f", timer(__)))^!_ +\
($++NF = log( $_ ) / log(_+_))^!_'
---------------------------------------------
timeout --foreground 1200 gfactor 49456902806087647575555655201
timeout --foreground 1200 gfactor 2445985235170800228886882843536511572299116327852398350401
49456902806087647575555655201: 49456902806087647575555655201 0.0047909999999 95.320158551927676171544590033590793609619140625