Last active
June 20, 2019 09:58
-
-
Save enfiskutensykkel/24feac70bcb797279144537ade95b67e to your computer and use it in GitHub Desktop.
Makefile Sieve of Eratosthenes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
### 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