Square form factorization: Difference between revisions
J draft
(Bugfix for FreeBasic 64-bit) |
(J draft) |
||
Line 944:
4611686018427387877 343242169 13435662733
</pre>
=={{header|J}}==
{{eff note|J|q:}}
J does not have an unsigned fixed width integer type, which is one of the reasons that (in J) this algorithm is less optimal than advertised:<lang J>sqff=: {{
s=. <.%:y
if. y=*:s do. s return. end.
for_D. (x:y)*/:~*/@>,{1,each}.p:i.5 do.
if. -.'integer'-:datatype D=. x:inv D do. break. end.
P=. <.%:D
Q=. 1, D-P*P
lim=. <:6*<.%:2*s
for_i. }.i.lim do.
b=. <.(+/0 _1{P)%{:Q
P=. P,|(b*{:Q)-{:P
Q=. Q,|(_2{Q)+b*-/_2{.P
if. 2|i do. if. (=<.&.%:){:Q do. break. end. end.
end.
if. i>:lim do. continue. end.
Q=. <.%:{:Q
b=. <.(-/0 _1{P)%Q
P=. ,(b*Q)+{:P
Q=. Q, <.|(D-*:P)%Q
whilst. ~:/_2{.P do.
b=. <.(+/0 _1{P)%{:Q
P=. P,|(b*{:Q)-{:P
Q=. Q,|(_2{Q)+b*-/_2{.P
end.
f=. y+.x:_2{Q
if. -. f e. 1,y do. f return. end.
end.
1
}}</lang>
Task examples:<lang J> task ''
2501: 61 * 41
12851: 71 * 181
13289: 137 * 97
75301: 293 * 257
120787: 43 * 2809
967009: 601 * 1609
997417: 257 * 3881
7091569: 2663 * 2663
13290059: 3119 * 4261
42854447: 9689 * 4423
223553581: 11213 * 19937
2027651281: 46061 * 44021
11111111111: 21649 * 513239
100895598169: 112303 * 898423
1002742628021 was not factored
60012462237239: 6862753 * 8744663
287129523414791: 6059887 * 47381993
9007199254740931: 10624181 * 847801751
11111111111111111: 2071723 * 5363222357
314159265358979323: 317213509 * 990371647
384307168202281507: 415718707 * 924440401
419244183493398773: 48009977 * 8732438749
658812288346769681: 62222119 * 10588072199
922337203685477563: 110075821 * 8379108103
1000000000000000127 was not factored
1152921505680588799: 139001459 * 8294312261
1537228672809128917 was not factored
4611686018427387877 was not factored</lang> where <lang J>task=: {{
for_num. nums do.
factor=. x:sqff num
if. 1=factor do. echo num,&":' was not factored'
else. echo num,&":': ',factor,&":' * ',":x:num%factor
end.
end.
}}
nums=: ".{{)n
2501
12851
13289
75301
120787
967009
997417
7091569
13290059
42854447
223553581
2027651281
11111111111
100895598169
1002742628021
60012462237239
287129523414791
9007199254740931
11111111111111111
314159265358979323
384307168202281507
419244183493398773
658812288346769681
922337203685477563
1000000000000000127
1152921505680588799
1537228672809128917
4611686018427387877x
}}-.LF</lang>
=={{header|jq}}==
| |||