Square form factorization: Difference between revisions
→{{header|Raku}}: Additional solution
(→{{header|Raku}}: Additional solution) |
|||
Line 1,168:
=={{header|Raku}}==
===A just for fun snail ..===
References: [https://en.wikipedia.org/wiki/Shanks%27s_square_forms_factorization#Algorithm Algorithm], [https://en.wikipedia.org/wiki/Shanks%27s_square_forms_factorization#Example_implementations C program example] from the WP page and also the pseudocode from [http://colin.barker.pagesperso-orange.fr/lpa/big_squf.htm here].
<lang perl6># 20210325 Raku programming solution
Line 1,278:
419244183493398773 = 48009977 * 8732438749
1537228672809128917 = 26675843 * 57626245319
</pre>
===Use NativeCall===
Use idea similar to the second approach from [https://rosettacode.org/wiki/Machine_code#Raku here], by compiling the C (Classical heuristic) entry to a shared library and then make use of the squfof routine.
squfof.raku
<lang perl6># 20210326 Raku programming solution
use NativeCall;
constant LIBSQUFOF = '/home/user/LibSQUFOF.so';
sub squfof(uint64 $n) returns uint64 is native(LIBSQUFOF) { * };
race for (
11111, # wikipedia.org/wiki/Shanks%27s_square_forms_factorization#Example
4558849, # example from talk page
# all of the rest are taken from the FreeBASIC entry
2501,12851,13289,75301,120787,967009,997417,7091569,13290059,
42854447,223553581,2027651281,11111111111,100895598169,1002742628021,
60012462237239, # = 6862753 * 8744663
287129523414791, # = 6059887 * 47381993
11111111111111111, # = 2071723 * 5363222357
384307168202281507, # = 415718707 * 924440401
1000000000000000127, # = 111756107 * 8948056861
9007199254740931, # = 10624181 * 847801751
922337203685477563, # = 110075821 * 8379108103
314159265358979323, # = 317213509 * 990371647
1152921505680588799, # = 139001459 * 8294312261
658812288346769681, # = 62222119 * 10588072199
419244183493398773, # = 48009977 * 8732438749
1537228672809128917, # = 26675843 * 57626245319
4611686018427387877, # = 343242169 * 13435662733
) -> \data {
given squfof(data) { say data, " = ", $_, " * ", data div $_ }
}</lang>
{{out}}<pre>gcc -Wall -fPIC -shared -o LibSQUFOF.so squfof.c
file LibSQUFOF.so
LibSQUFOF.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=f7f9864e5508ba1de80cbc6e2f4d789f4ec448e9, not stripped
raku -c squfof.raku && time ./squfof.raku
Syntax OK
11111 = 41 * 271
4558849 = 383 * 11903
2501 = 61 * 41
12851 = 71 * 181
13289 = 97 * 137
75301 = 293 * 257
120787 = 43 * 2809
967009 = 1609 * 601
997417 = 257 * 3881
7091569 = 2663 * 2663
13290059 = 3119 * 4261
42854447 = 4423 * 9689
223553581 = 11213 * 19937
2027651281 = 44021 * 46061
11111111111 = 21649 * 513239
100895598169 = 112303 * 898423
1002742628021 = 1 * 1002742628021
60012462237239 = 6862753 * 8744663
287129523414791 = 6059887 * 47381993
11111111111111111 = 2071723 * 5363222357
384307168202281507 = 415718707 * 924440401
1000000000000000127 = 111756107 * 8948056861
9007199254740931 = 10624181 * 847801751
922337203685477563 = 110075821 * 8379108103
314159265358979323 = 317213509 * 990371647
1152921505680588799 = 139001459 * 8294312261
658812288346769681 = 62222119 * 10588072199
419244183493398773 = 48009977 * 8732438749
1537228672809128917 = 26675843 * 57626245319
4611686018427387877 = 343242169 * 13435662733
real 0m0.784s
user 0m0.716s
sys 0m0.056s
</pre>
| |||