/prog/ - question about some prolog code

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?
question about some prolog code

1 Name: Anonymous 2009-03-20 8:20

Name: Anonymous 2009-03-20 8:20
