Skip to content

Instantly share code, notes, and snippets.

@enfiskutensykkel
Last active June 20, 2019 09:58
Show Gist options
  • Save enfiskutensykkel/24feac70bcb797279144537ade95b67e to your computer and use it in GitHub Desktop.
Save enfiskutensykkel/24feac70bcb797279144537ade95b67e to your computer and use it in GitHub Desktop.
Makefile Sieve of Eratosthenes
### List operators
slice = $(wordlist 2,$(words $1),$1)
replicate = $(if $(call eq,$(words $4),$1),$3,$(call replicate,$1,$2,$3 $2,$(words $4) $4))
rotate = $(call slice,$1) $(firstword $1)
map = $(if $2,$(call map,$1,$(call slice,$2),$3,$4 $(call $1,$3,$(firstword $2),$4)),$4)
fold = $(if $2,$(call fold,$1,$(call slice,$2),$(call $1,$3,$(firstword $2))),$3)
zip = $(if $2,$(call zip,$1,$(call slice,$2),$(call rotate,$3),$4 $(call $1,$(firstword $2),$(firstword $3))),$4)
### Arithmetic operators
inc = $(words $(call replicate,$1,_) _)
dec = $(words $(call slice,$(call replicate,$1,_)))
max = $(words $(subst __,_,$(join $(call replicate,$1,_),$(call replicate,$2,_))))
min = $(words $(subst __,_,$(filter __,$(join $(call replicate,$1,_),$(call replicate,$2,_)))))
eq = $(filter $1,$2)
gt = $(filter-out $2,$(call max,$1,$2))
gte = $(call gt,$1,$2)$(call eq,$1,$2)
add = $(words $(call replicate,$1,_) $(call replicate,$2,_))
sub = $(words $(filter-out __,$(join $(call replicate,$1,_),$(call replicate,$2,_))))
mul = $(words $(call replicate,$1,$(call replicate,$2,_)))
div = $(if $(call gte,$1,$2),$(call add,1,$(call div,$(call sub,$1,$2),$2)),0)
quart = $(call div,$1,4)
double = $(call mul,2,$1)
isqrt_cand = $(if $(call gt,$(call mul,$(call inc,$1),$(call inc,$1)),$2),$1,$(call inc,$1))
isqrt = $(if $(call gte,$1,2),$(call isqrt_cand,$(call double,$(call isqrt,$(call quart,$1))),$1),$1)
### Main program body
head = $(firstword $2)
count = $(words $3)
# Repeat function N times
loop = $(call fold,$2,$(call map,count,$(call replicate,$1,_)),$3)
# Skip into a list
skip = $(call loop,$1,slice,$2)
# Eliminate multiples of a number (sieve)
cycle = $(call slice,$(call replicate,$1,_)) 0
eliminate = $(if $(call eq,$2,0),0,$1)
sieve = $(call zip,head,$(call replicate,$(call double,$1),_),$2) $(call zip,eliminate,$(call skip,$(call double,$1),$2),$(call loop,$(call dec,$1),rotate,$(call cycle,$1)))
# Helper function to call our sieve function
dispatch = $(if $(call gt,$2,1),$(call sieve,$2,$1),$1)
# Initial bootstrapping
n := 100
s := $(call isqrt,$(n))
numbers := $(call map,count,$(call replicate,$(n),_))
primes := $(filter-out 0,$(call skip,2,$(call loop,$(s),dispatch,$(numbers))))
println = $(info $2)
### Targets
.PHONY: all
all: ; $(call map,println,$(primes))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment