Joost Behrends wrote:
apfelmus writes:
Huh? p intsqrt n is evaluated just as often as p*p n , with
changing n . Why would that be less expensive? Btw, the code above
test for r==0 first, which means that the following p*p n is
tested exactly once for every prime candidate p .
On 12/20/07, Joost Behrends [EMAIL PROTECTED] wrote:
The syntax with the block in
newtype State s a = State { runState :: s - (a,s) }
is not in the tutorials i read.
newtype creates a new type which is treated exactly the same as an existing
type at runtime, but which is distinct to the
Joost Behrends wrote:
apfelmus writes:
How about separating the candidate prime numbers from the recursion
factorize :: Integer - [Integer]
factorize = f primes'
where
primes' = 2:[3,5..]
f (p:ps) n
| r == 0= p : f (p:ps) q
| p*p n = [n]
Am Freitag, 21. Dezember 2007 11:33 schrieb apfelmus:
Joost Behrends wrote:
apfelmus writes:
How about separating the candidate prime numbers from the recursion
factorize :: Integer - [Integer]
factorize = f primes'
where
primes' = 2:[3,5..]
f (p:ps) n
@apfelmus,
please read my code. I introduced DivIter to separate divstep from divisions.
But it stores intsqrt dividend also. Thus the sqrt is only recomputed, when a
new factor is found.
Concerning primes': With the sieve of Eratosthenes we cannot make a lazy list,
we need the whole list at any
@apfelmus,
please read my code. I introduced DivIter to separate divstep from divisions.
But it stores intsqrt dividend also. Thus the sqrt is only recomputed, when a
new factor is found.
Concerning primes': With the sieve of Eratosthenes we cannot make a lazy list,
we need the whole list at any
Daniel Fischer wrote:
apfelmus writes:
| r == 0= p : f (p:ps) q
| p*p n = [n]
| otherwise = f ps n
However, when you do the sensible thing (which Joost did) and have the intsqrt
a parameter of the function, like in
factorize :: Integer - [Integer]
apfelmus apfelmus at quantentunnel.de writes:
Huh? p intsqrt n is evaluated just as often as p*p n , with
changing n . Why would that be less expensive? Btw, the code above
test for r==0 first, which means that the following p*p n is
tested exactly once for every prime
Joost Behrends wrote:
since about three weeks i am learning Haskell now. One of my first exercises is
to decompose an Integer into its primefactors.
How about separating the candidate prime numbers from the recursion
factorize :: Integer - [Integer]
factorize = f primes'
where
Albert Y. C. Lai trebla at vex.net writes:
Theoretically the recursions in
oddFactors k n | otherwise = oddFactors (k+2) n
and
(*) divisions y |divisor y = bound y = divisions (divstep y)
do not cost stack space. They are tail recursions too!
In general similar tail
apfelmus apfelmus at quantentunnel.de writes:
How about separating the candidate prime numbers from the recursion
factorize :: Integer - [Integer]
factorize = f primes'
where
primes' = 2:[3,5..]
f (p:ps) n
| r == 0= p : f (p:ps) q
| p*p n
On 12/20/07, Joost Behrends [EMAIL PROTECTED] wrote:
makes a DESTRUCTIVE UPDATE of the DivIters (by put) and this kind of
recursion
seems not to remember itself (as i have understood, that is achieved by
tail recursion). I just didn't like making DivIters to States.
It's kind of lying code.
Joost Behrends wrote:
@Daniel: no, this doesn't solve the stack problem. These are the primefactors of
2^120+1: [97,257,673,394783681,4278255361,46908728641].
oddFactors k n | otherwise = oddFactors (k+2) n
could eventually push 394783681-673 function calls onto the stack before finding
the
Daniel Fischer daniel.is.fischer at web.de writes:
Am Dienstag, 18. Dezember 2007 17:26 schrieb Joost Behrends:
Hi,
since about three weeks i am learning Haskell now. One of my first
excercises is to decompose an Integer into its primefactors. I already
posted discussion on the
14 matches
Mail list logo