# Total cycles for examples: 29,566,640
**Note**: the program depends on the following patch: https://github.com/orlp/golf-cpu/pull/8
It cubes the input number in the algorithm, so the input can't be larger than around `2^21`.
Cycle count for example input:
Input Cycles
1 153
5 75
8 773
24 1,528
100 3,185
1080 27,608
468719 9,676,846
468720 9,764,814
468721 10,091,658
I'm using an [algorithm I found on OEIS](https://oeis.org/A034836), which does the following:
cuboids(n):
if is_prime(n):
return 1
res = 0
for d in divisors(n):
if d^3 <= n:
for d0 in divisors(n/d):
if d0^2 <= n/d:
res += 1
if d0 < d:
res -= 1
return res
This might actually be slower than just trying every divisor combination and checking if `d1 <= d2 <= d3`, however the bottle-neck is finding the prime anyway.
Divisors are found by using the prime factorization of the number. I'm using the same method to build an array of all primes below the input number as I used in [the previous problem](http://codegolf.stackexchange.com/questions/52489/the-golf-cpu-golfing-challenge-prime-partitions).
Run with:
python3 assemble.py 52489-cuboids.golf
python3 golf.py -d 52489-cuboids.bin x=<INPUT>
Output will be in the `t` register.
Example run:
$ python3 golf.py -d 52489-cuboids.bin x=1080 | grep 'Execution\|t: '
Execution terminated after 27608 cycles with exit code 0. Register file at exit:
t: 52 0x34
Code:
call build_primes
mov q, x
call is_prime
jnz prime, a
shl m, x, 3
add m, m, 8
call divisors
mov y, x
mov k, l
mov t, 0
mov p, m
outer_loop:
cmp a, p, k
jnz done, a
lw d, p
add p, p, 8
mulu a, r, d, d
mulu a, r, a, d
lequ a, a, y
jz outer_loop, a
divu x, r, y, d
mov m, k
call divisors
mov q, m
inner_loop:
cmp a, q, l
jnz outer_loop, a
lw o, q
add q, q, 8
mulu a, r, o, o
lequ a, a, x
jz skip1, a
inc t
skip1:
leu a, o, d
jz inner_loop, a
dec t
jmp inner_loop
done:
halt 0
prime:
mov t, 1
halt 0
# Input: x, m
# Output: l
# x: input number
# m: memory location to store divisors
# l: memory location where last divisor is stored + 8
divisors:
sw m, 1
add l, m, 8
mov p, 2
divisors_outer:
mov q, 1
push z, 0
divisors_inner:
divu y, r, x, p
jnz divisors_not_divisible, r
mulu q, r, q, p
push z, q
mov x, y
jmp divisors_inner
divisors_not_divisible:
mov w, l
divisors_not_divisible_outer:
mov v, m
pop t, z
jz divisors_not_divisible_last, t
divisors_not_divisible_inner:
cmp a, v, w
jnz divisors_not_divisible_outer, a
lw s, v
mulu a, r, s, t
sw l, a
add l, l, 8
add v, v, 8
jmp divisors_not_divisible_inner
divisors_not_divisible_last:
shl i, p, 3
lw p, i
cmp a, x, 1
jz divisors_outer, a
ret l
# Input: x
# Memory layout: [-1, -1, 3, 5, -1, 7, -1, 11, ...]
# x: max integer
# p: current prime
# y: pointer to last found prime
# i: current integer
build_primes:
sw 0, -1
sw 8, -1
sw 16, 1
mov y, 16
mov p, 2
build_primes_outer:
mulu i, r, p, p
jnz build_primes_final, r
geu a, i, x
jnz build_primes_final, a
build_primes_inner:
shl m, i, 3
sw m, -1
add i, i, p
geu a, i, x
jz build_primes_inner, a
build_primes_next:
inc p
shl m, p, 3
lw a, m
jnz build_primes_next, a
sw y, p
mov y, m
sw y, 1
jmp build_primes_outer
build_primes_final:
inc p
geu a, p, x
jnz build_primes_ret, a
shl m, p, 3
lw a, m
jnz build_primes_final, a
sw y, p
mov y, m
sw y, 1
jmp build_primes_final
build_primes_ret:
ret
# Input: q
# Output: a
is_prime:
shl m, q, 3
lw a, m
neq a, a, -1
ret a