Name: Anonymous 2009-03-20 8:20
why is this:
product([], 1).
product([H|T], X) :- product(T, Y), X is H * Y.
factorial(N, R) :- numlist(2, N, Ns), product(Ns, R).
so much faster than this:
no_multiple(P, N) :- N rem P =\= 0.
sieve([], []).
sieve([P|Ns0], [P|Rest]) :-
include(no_multiple(P), Ns0, Ns),
sieve(Ns, Rest).
primes_upto(N, Ps) :-
numlist(2, N, Ps0),
sieve(Ps0, Ps).
bitcount(0, 0).
bitcount(N, R) :-
N2 is N >> 1,
B is N rem 2,
bitcount(N2, C),
R is B + C.
product([], 1).
product([H|T], X) :- product(T, Y), X is H * Y.
swingAfilter(Q, P, PR, Rs) :-
X is Q // PR,
( X =@= 0 ->
( P =@= 0 -> Rs is []; Rs is [P] );
P0 is P * PR ** (X rem 2),
swingAfilter(X, P0, PR, Rs) ).
swingAfilter1(Q, PR, Rs) :- swingAfilter(Q, 1, PR, Rs).
swing(N, S) :-
N < 33 ->
nth0(N, [1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 300540195, 300540195], S);
primes_upto(N, Ps0),
R is floor(sqrt(N)),
R1 is R + 1,
numlist(R1, N, NsA),
[2|PsA0] = Ps0,
subtract(PsA0, NsA, PsA1),
length(PsA1, L),
length(Ns, L),
list_to_set(Ns, [N]),
maplist(swingAfilter1, Ns, PsA1, PsA),
N3 is N // 3,
numlist(R1, N3, NsB),
intersection(Ps0, NsB, PsB0),
findall(P, (member(P, PsB0), (N // P) rem 2 =:= 1), PsB),
N2 is N >> 1,
numlist(2, N2, NsC),
subtract(Ps0, NsC, PsC),
flatten([PsA, PsB, PsC], Ps),
product(Ps, S).
recfactorial(0, 1).
recfactorial(1, 1).
recfactorial(N, R) :-
N2 is N >> 1,
swing(N, S),
recfactorial(N2, F),
R is F ** 2 * S.
factorial(N, R) :-
N < 20 ->
numlist(2, N, Ns),
product(Ns, R);
recfactorial(N, F),
bitcount(N, B),
R is (F << (N - B)).
?
prime-swing should be faster than stupid O(n) multiplication, shouldn't it?
product([], 1).
product([H|T], X) :- product(T, Y), X is H * Y.
factorial(N, R) :- numlist(2, N, Ns), product(Ns, R).
so much faster than this:
no_multiple(P, N) :- N rem P =\= 0.
sieve([], []).
sieve([P|Ns0], [P|Rest]) :-
include(no_multiple(P), Ns0, Ns),
sieve(Ns, Rest).
primes_upto(N, Ps) :-
numlist(2, N, Ps0),
sieve(Ps0, Ps).
bitcount(0, 0).
bitcount(N, R) :-
N2 is N >> 1,
B is N rem 2,
bitcount(N2, C),
R is B + C.
product([], 1).
product([H|T], X) :- product(T, Y), X is H * Y.
swingAfilter(Q, P, PR, Rs) :-
X is Q // PR,
( X =@= 0 ->
( P =@= 0 -> Rs is []; Rs is [P] );
P0 is P * PR ** (X rem 2),
swingAfilter(X, P0, PR, Rs) ).
swingAfilter1(Q, PR, Rs) :- swingAfilter(Q, 1, PR, Rs).
swing(N, S) :-
N < 33 ->
nth0(N, [1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 300540195, 300540195], S);
primes_upto(N, Ps0),
R is floor(sqrt(N)),
R1 is R + 1,
numlist(R1, N, NsA),
[2|PsA0] = Ps0,
subtract(PsA0, NsA, PsA1),
length(PsA1, L),
length(Ns, L),
list_to_set(Ns, [N]),
maplist(swingAfilter1, Ns, PsA1, PsA),
N3 is N // 3,
numlist(R1, N3, NsB),
intersection(Ps0, NsB, PsB0),
findall(P, (member(P, PsB0), (N // P) rem 2 =:= 1), PsB),
N2 is N >> 1,
numlist(2, N2, NsC),
subtract(Ps0, NsC, PsC),
flatten([PsA, PsB, PsC], Ps),
product(Ps, S).
recfactorial(0, 1).
recfactorial(1, 1).
recfactorial(N, R) :-
N2 is N >> 1,
swing(N, S),
recfactorial(N2, F),
R is F ** 2 * S.
factorial(N, R) :-
N < 20 ->
numlist(2, N, Ns),
product(Ns, R);
recfactorial(N, F),
bitcount(N, B),
R is (F << (N - B)).
?
prime-swing should be faster than stupid O(n) multiplication, shouldn't it?