[Haskell-cafe] Re: Optimization fun

[Lennart Augustsson]

Many architectures gives both the quotient and remainder when you use  
the division instruction, so divMod (quotRem) shouldn't cost more  
than a div or mod.  But if the code generator takes advantage of that  
is another matter.

On Feb 12, 2007, at 02:32 , Matthew Brecknell wrote:

> I wrote:
>> primes :: [Int]
>> primes = 2 : filter isPrime [3,5..] where
>>   f x p r = x < p*p || mod x p /= 0 && r
>>   isPrime x = foldr (f x) True primes
>
> Creighton Hogg wrote:
>> This looks really slick to me, thanks.
>> So if I understand correctly, the main thing that makes this work  
>> is that
>> &&'ing the test with the accumulator r will make it bail out of  
>> the fold
>> as
>> soon as one of the two tests is failed because the result must be  
>> False?
>
> Yes. Look at the definition of %% and ||:
>
> True && x = x
> False && _ = False
>
> True || _ = True
> False || x = x
>
> The second argument of && or || won't be evaluated if the first
> determines the result.
>
> And this brings you back to the point made by Lennart and others about
> why foldl is the wrong choice: foldl won't allow you to take advantage
> of this short-circuiting. Write out a few steps of each type of  
> fold if
> you don't understand why.
>
> Note, I wouldn't call r an accumulator: it's just the rest of the fold
> (which, as you've pointed out, only needs to be evaluated if you don't
> already know the result).
>
> Since writing the above, I've realised that the second argument of the
> foldr most certainly shouldn't be True. One might be able to argue  
> that
> False would be more correct, but really it's irrelevant since we know
> we'll never reach the end of the list of primes. What I found most
> surprising was that replacing True with undefined made the calculation
> about 10% faster (GHC 6.4.2, amd64):
>
>> primes :: [Int]
>> primes = 2 : filter isPrime [3,5..] where
>>   f x p r = x < p*p || mod x p /= 0 && r
>>   isPrime x = foldr (f x) undefined primes
>
> Comparing this to DavidA's solution: At least on my platform,  
> testing (x
> < p*p) is significantly quicker than using quotRem/divMod. I suspect
> quotRem actually requires the division to be performed twice, and
> multiplication is faster than division.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe