Square form factorization: Difference between revisions

===Based on Wp===

From the Wikipedia entry for Shanks's square forms factorization [[//en.wikipedia.org/wiki/Shanks%27s_square_forms_factorization.]]

#include <stdio.h>

 

}

}

<pre>

Integer 2501 has factors 61 and 41

===Classical heuristic===

See [[Talk:Square_Form_Factorization|Discussion]].

//Classical heuristic. Tested: tcc 0.9.27

#include <math.h>

else printf("f = %llu N/f = %llu\n\n", f, N/f);

}

 

{{out|Showing problem cases only}}

 

=={{header|FreeBASIC}}==

'subject: Shanks's square form factorization:

' ambiguous forms of discriminant 4N

 

print "total time:"; csng(timer - tim); " s"

 

{{out|Examples}}

 

Rather than juggling with big.Int, I've just allowed the two 'awkward' cases to fail.

 

import (

fmt.Printf("%-20d %-10d %s\n", N, fact, quot)

}

 

{{out}}

=={{header|J}}==

{{eff note|J|q:}}

s=. <.%:y

if. y=*:s do. s return. end.

end.

1

 

2501: 61 * 41

12851: 71 * 181

1152921505680588799: 139001459 * 8294312261

1537228672809128917 was not factored

for_num. nums do.

factor=. x:sqff num

1537228672809128917

4611686018427387877x

 

=={{header|jq}}==

 

'''Preliminaries'''

# subfunction expects [a,b] as input

# i.e. a ~ .[0] and b ~ .[1]

then irt

else "isqrt requires a non-negative integer for accuracy" | error

'''The Tasks'''

[

1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11

| [$N, $fact, $quot]

end

{{out}}

<pre>

=={{header|Julia}}==

Modified from Wikipedia's article at [[https://en.wikipedia.org/wiki/Shanks%27s_square_forms_factorization]]

multiplier = T.([1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11])

s = T(round(sqrt(n)))

println(factr == 0 ? "fail" : n ÷ factr)

end

<pre>

Integer Factor Quotient

=={{header|Nim}}==

{{trans|Phix}}

 

const M = [uint64 1, 3, 5, 7, 11]

let f = squfof(n)

let res = if f == 1: "fail" else: &"{f:<10} {n div f}"

 

{{out}}

{{trans|Raku}}

{{libheader|ntheory}}

use warnings;

use feature 'say';

elsif ($v == 1) { say 'The number ' . $data . ' is a prime.' }

else { say "$data = " . join ' * ', sort {$a <=> $b} $v, int $data/int($v) }

{{out}}

<pre>11111 = 41 * 271

=={{header|Phix}}==

{{trans|C|<small>(Classical heuristic - fixes the two incorrectly failing cases of the previous version)</small>}}

<span style="color: #000080;font-style:italic;">--requires(64) -- (decided to limit 32-bit explicitly instead)</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">MxN</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power<span style="color: #0000FF;">(<span style="color: #000000;">2<span style="color: #0000FF;">,<span style="color: #008080;">iff<span style="color: #0000FF;">(<span style="color: #7060A8;">machine_bits<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">=<span style="color: #000000;">32<span style="color: #0000FF;">?<span style="color: #000000;">53<span style="color: #0000FF;">:<span style="color: #000000;">63<span style="color: #0000FF;">)<span style="color: #0000FF;">)<span style="color: #0000FF;">,</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for

{{out}}

<small>(on 64-bit, whereas the last 10 entries, ie 11111111111111111 on, are simply omitted on 32-bit)</small>

===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].

 

my @multiplier = ( 1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11 );

}

}

{{out}}

<pre>

 

squfof.raku

 

use NativeCall;

) -> \data {

given squfof(data) { say data, " = ", $_, " * ", data div $_ }

{{out}}<pre>gcc -Wall -fPIC -shared -o LibSQUFOF.so squfof.c

file LibSQUFOF.so

within the

<br>REXX program) &nbsp; is because the number being tested is a prime &nbsp; (1,002,742,628,021).

numeric digits 100 /*ensure enough decimal digits.*/

call dMults 1,3,5,7,11,3*5,3*7,3*11,5*7,5*11,7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11

if r\==1 then if r\==n then return r

end /*#*/

{{out|output|text=&nbsp; when using the internal default input:}}

<pre>

 

Even so, there are two examples which fail (1000000000000000127 and 1537228672809128917) because the code is unable to process enough 'multipliers' before an overflow situation is encountered. To deal with this, the program automatically switches to BigInt to process such cases.

import "/big" for BigInt

import "/fmt" for Fmt

var quot = (fact.isZero) ? "fail" : (N / fact).toString

Fmt.print("$-20s $-10s $s", N, fact, quot)

 

{{out}}