Dear HCafe-ers, Yesterday I decided to take a look at the most recent Euler problem, number 249, and give it a shot. I have a couple of computers at home, a Dell laptop and a desktop. I compiled this message with ghc -O2 --make ex429.lhs and ran it on each machine. On the Dell I get: time ./ex429 [650,16900,547924,27396200,746640991,773879749,683631060] [650,16900,547924,27396200,746640991,773879749,683631060] 136342232 ./ex429 8.66s user 0.02s system 99% cpu 8.695 total When I run this exact same file on the desktop, I get: time ./ex429 [650,16900,547924,27396200,746640991,773879749,683631060] [650,16900,547924,27396200,746640991,773879749,683631060] 98792821 ./ex429 6.50s user 0.03s system 99% cpu 6.537 total Which happens to be the right answer. But WHY is the output from the Dell different? Machine info is at the bottom of this message.
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE FlexibleContexts #-} {-# OPTIONS -O2 -optc-O #-} {- Sum of squares of unitary divisors Problem 429 A unitary divisor d of a number n is a divisor of n that has the property gcd(d, n/d) = 1. The unitary divisors of 4! = 24 are 1, 3, 8 and 24. The sum of their squares is 12 + 32 + 82 + 242 = 650.
Let S(n) represent the sum of the squares of the unitary divisors of n. Thus S(4!)=650.
Find S(100 000 000!) modulo 1 000 000 009.
-}
import Control.Monad.ST import Data.Array.ST import Data.Array.IArray as I import Data.Array.Unboxed as U import Data.Word import Data.Ord import Data.List
allfactors n = [ i | i <- [1..n] , n `mod` i == 0]
factorial n = product [1..n] ud0 n = let nf = factorial n a = allfactors nf b = filter (\x -> gcd x (nf `div` x) == 1) a in b
ud1 = sum . map (\x -> x*x) . ud0 ansSlow n = ud1 n `mod` (fromIntegral modulus)
largestExponentInFactorial n p = let a = [ n `div` (p^i) | i <- [1..] ] b = takeWhile (>0) a in sum b
modProduct :: [Int] -> Int modProduct = foldl' (\a b -> times a b modulus) 1
pA n = primesA (fromIntegral n)
primesN :: Int -> [Int] primesN n = map fromIntegral $ primeS (pA n)
times :: Int -> Int -> Int -> Int times x y n = let x1 = fromIntegral x :: Integer y1 = fromIntegral y :: Integer n1 = fromIntegral n :: Integer result = fromIntegral $! x1 * y1 `mod` n1 in result
fastPower :: Int -> Int -> Int -> Int fastPower x 0 modulus = 1 fastPower x 1 modulus = x `mod` modulus fastPower x n modulus | even n = fastPower (times x x modulus) (n `div` 2) modulus | otherwise = (times x (fastPower x (n-1) modulus)) modulus
foldFun :: Int -> Int -> Int foldFun n p = let a = largestExponentInFactorial n p b = fastPower p a modulus c = times b b modulus + 1 in c
ff :: Int -> [Int] -> Int ff n = foldl' (\a p -> times a (foldFun n p) modulus) 1
ans n = let ps = primeS $ primesA n -- ps = takeWhile (<= n) primes in ff n ps
modulus = 1000000009 :: Int main = do print $ map ans [4..10] print $ map ansSlow [4..10] print $ ans 100000000
{-
intended Usage:
pA = primesA (10^9) primes = primeS pA isPrime = isPrimE pA
-}
sieve :: STUArray s Int Bool -> Int -> Int -> ST s (STUArray s Int Bool) sieve !a !m !n | n == m = return a | otherwise = do e <- readArray a (fromIntegral n) if e then let loop !j | j <= m = writeArray a (fromIntegral j) False >> loop (j+n) | otherwise = sieve a m (n+1) in loop (n+n) else sieve a m (n+1)
primesA :: Int -> UArray Int Bool primesA sizeN = runSTUArray (do a <- newArray (0,sizeN) True :: ST s (STUArray s Int Bool) writeArray a 0 False writeArray a 1 False sieve a sizeN 2)
primeS :: (IArray a1 Bool, Ix a) => a1 a Bool -> [a] primeS primeArray = map fst $ filter (\x -> snd x) (assocs primeArray)
isPrimE :: (IArray a e, Ix i) => a i e -> i -> e isPrimE primeArray n = primeArray I.! n
AMD-64 Desktop uname -a Linux myth 3.2.0-4-amd64 #1 SMP Debian 3.2.41-2+deb7u2 x86_64 GNU/Linux ghc --version The Glorious Glasgow Haskell Compilation System, version 7.6.2 hwinfo --cpu 01: None 00.0: 10103 CPU [Created at cpu.304] Unique ID: rdCR.j8NaKXDZtZ6 Hardware Class: cpu Arch: X86-64 Vendor: "AuthenticAMD" Model: 21.1.2 "AMD FX(tm)-4100 Quad-Core Processor " Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,mmx,fxsr,sse,sse2,ht,syscall,nx,mmxext,fxsr_opt,pdpe1gb,rdtscp,lm,constant_tsc,rep_good,nopl,nonstop_tsc,extd_apicid,aperfmperf,pni,pclmulqdq,monitor,ssse3,cx16,sse4_1,sse4_2, Clock: 1400 MHz BogoMips: 7248.25 Cache: 2048 kb Units/Processor: 4 Config Status: cfg=new, avail=yes, need=no, active=unknown 02: None 01.0: 10103 CPU [Created at cpu.304] Unique ID: wkFv.j8NaKXDZtZ6 Hardware Class: cpu Arch: X86-64 Vendor: "AuthenticAMD" Model: 21.1.2 "AMD FX(tm)-4100 Quad-Core Processor " Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,mmx,fxsr,sse,sse2,ht,syscall,nx,mmxext,fxsr_opt,pdpe1gb,rdtscp,lm,constant_tsc,rep_good,nopl,nonstop_tsc,extd_apicid,aperfmperf,pni,pclmulqdq,monitor,ssse3,cx16,sse4_1,sse4_2, Clock: 3600 MHz BogoMips: 9201.22 Cache: 2048 kb Units/Processor: 4 Config Status: cfg=new, avail=yes, need=no, active=unknown 03: None 02.0: 10103 CPU [Created at cpu.304] Unique ID: +rIN.j8NaKXDZtZ6 Hardware Class: cpu Arch: X86-64 Vendor: "AuthenticAMD" Model: 21.1.2 "AMD FX(tm)-4100 Quad-Core Processor " Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,mmx,fxsr,sse,sse2,ht,syscall,nx,mmxext,fxsr_opt,pdpe1gb,rdtscp,lm,constant_tsc,rep_good,nopl,nonstop_tsc,extd_apicid,aperfmperf,pni,pclmulqdq,monitor,ssse3,cx16,sse4_1,sse4_2, Clock: 1400 MHz BogoMips: 7253.01 Cache: 2048 kb Units/Processor: 4 Config Status: cfg=new, avail=yes, need=no, active=unknown 04: None 03.0: 10103 CPU [Created at cpu.304] Unique ID: 4zLr.j8NaKXDZtZ6 Hardware Class: cpu Arch: X86-64 Vendor: "AuthenticAMD" Model: 21.1.2 "AMD FX(tm)-4100 Quad-Core Processor " Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,mmx,fxsr,sse,sse2,ht,syscall,nx,mmxext,fxsr_opt,pdpe1gb,rdtscp,lm,constant_tsc,rep_good,nopl,nonstop_tsc,extd_apicid,aperfmperf,pni,pclmulqdq,monitor,ssse3,cx16,sse4_1,sse4_2, Clock: 1400 MHz BogoMips: 6931.30 Cache: 2048 kb Units/Processor: 4 Config Status: cfg=new, avail=yes, need=no, active=unknown ------------------------------------------------------------------------ Dell Laptop uname -a Linux dell 3.2.0-4-amd64 #1 SMP Debian 3.2.41-2 x86_64 GNU/Linux ghc --version The Glorious Glasgow Haskell Compilation System, version 7.6.3 01: None 00.0: 10103 CPU [Created at cpu.304] Unique ID: rdCR.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3987.12 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown 02: None 01.0: 10103 CPU [Created at cpu.304] Unique ID: wkFv.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3986.91 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown 03: None 02.0: 10103 CPU [Created at cpu.304] Unique ID: +rIN.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3986.92 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown 04: None 03.0: 10103 CPU [Created at cpu.304] Unique ID: 4zLr.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3986.92 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown 05: None 04.0: 10103 CPU [Created at cpu.304] Unique ID: 94PJ.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3986.91 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown 06: None 05.0: 10103 CPU [Created at cpu.304] Unique ID: EBSn.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3986.92 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown 07: None 06.0: 10103 CPU [Created at cpu.304] Unique ID: JIVF.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3986.91 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown 08: None 07.0: 10103 CPU [Created at cpu.304] Unique ID: OPYj.j8NaKXDZtZ6 Hardware Class: cpu Arch: Intel Vendor: "GenuineIntel" Model: 6.42.7 "Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz" Features: fpu,vme,de,pse,tsc,msr,pae,mce,cx8,apic,sep,mtrr,pge,mca,cmov,pat,pse36,clflush,dts,acpi,mmx,fxsr,sse,sse2,ss,ht,tm,pbe,syscall,nx,rdtscp,lm,constant_tsc,arch_perfmon,pebs,bts,nopl,xtopology,nonstop_tsc,aperfmperf,pni,pclmulqdq,dtes64,monitor,ds_cpl,vmx,e Clock: 800 MHz BogoMips: 3986.91 Cache: 6144 kb Units/Processor: 16 Config Status: cfg=new, avail=yes, need=no, active=unknown -- Best wishes, Henry Laxen