Zeckendorf representation (fibonacci base)

Fun video on number representation based on Fibonacci numbers.

Of course, we want to use these numbers at assemble-time.

Code:

include 'fibonacci.inc'

calminstruction to_zeckendorf? result_var*, input_val*
    local value, idx, current_fib, res
    local sym_ptr

    compute value, input_val
    compute res, 0

    call Fibonacci.EnsureValue, value
    compute idx, F_limit

    scan_loop:
        arrange sym_ptr, =F.#idx
        compute current_fib, sym_ptr

        check current_fib <= value
        jno skip_bit

        compute value, value - current_fib
        compute res, res or (1 shl idx)

    skip_bit:
        check idx > 0
        jno done
        compute idx, idx - 1
        jump scan_loop

    done:
        publish result_var, res
end calminstruction

calminstruction from_zeckendorf? result_var*, z_bitmap*
    local accum, temp_map, idx, bit_is_set
    local sym_ptr, fib_val
    
    compute accum, 0
    check z_bitmap
    jno zero
    compute temp_map, z_bitmap
    compute idx, 0

    ; Ensure table exists up to highest bit index
    local max_bit_idx
    compute max_bit_idx, bsr z_bitmap
    call Fibonacci.Grow, max_bit_idx

    decode_loop:
        compute bit_is_set, temp_map and 1
        check bit_is_set
        jno next_bit

        arrange sym_ptr, =F.#idx
        compute fib_val, sym_ptr
        compute accum, accum + fib_val

    next_bit:
        compute temp_map, temp_map shr 1
        compute idx, idx + 1
        
        check temp_map > 0
        jyes decode_loop
zero:
    publish result_var, accum
end calminstruction

... all Zeckendorf representations can be compressed by converting 01 bit pairs to 1.

; If the compressed Zeckendorf representation in RCX can be represented then ; the carry flag is clear and RAX is the value. zeck_compressed_to_u64: mov edx, 1 ; F2 mov r8d, 2 ; F3 xor eax, eax ; zero result .more: jrcxz .okay shr rcx, 1 jnc .0 .1: add rax, rdx jc .overflowed xadd r8, rdx ; fibonacci step: (F_k, F_{k+1}) -> (F_{k+1}, F_{k+2}) jc .overflow .0: xadd r8, rdx ; fibonacci step: (F_k, F_{k+1}) -> (F_{k+1}, F_{k+2}) jnc .more .overflow: ; forward carry flag unless RCX is zero jrcxz .okay .overflowed: retn .okay: clc retn