Bits of integer

[Albert Chan]

(12-15-2022 04:08 PM)Thomas Klemm Wrote:  Can we expect your explanations in APL instead of Lua from now on?

Lua is still my favorite.

I don't like write-once language, with comments that is much longer than code.
Any editing of code, you then have to correct for old comments.

The Law of Leaky Abstractions - Joel on Software

Quote:All non-trivial abstractions, to some degree, are leaky.
Abstractions fail. Sometimes a little, sometimes a lot. There’s leakage. Things go wrong.
It happens all over the place when you have abstractions. Here are some examples ...

Devlin's Angle, Base Consideration, Feb 1996

Quote:Playing with arithmetic having negative bases is an amusing classroom exercise, but, strange as it may seem, a computer was once built that used "-2" base arithmetic. It was the UMC-1, a Polish-made computer of the late 1950s and early 1960s, of which several dozen were made and installed.

      base ← ⊥⍣¯1
      ¯2 base 123
DOMAIN ERROR

APL code cannot convert to base -2. It may take lots of work to fix.

Same problem solved in Lua is easy.

Code:

function base(n, b)
    b = b or 10
    local T, i, B = {}, 0, (b<0 or n<0) and -b or b
    while n~=0 do i=i+1; T[i]=n%B; n=(n-T[i])/b end -- digits of n, in base b
    for j=1,i/2 do T[i],T[j] = T[j],T[i]; i=i-1 end -- reverse digits
    return T
end

lua> require'pprint'
lua> pprint(base(123, -2)) -- 9 bits
{ 1, 1, 0, 0, 0, 1, 1, 1, 1 }
lua> pprint(base(123, 2)) -- 7 bits
{ 1, 1, 1, 1, 0, 1, 1 }

For base 2, we can directly lookup binary exponent.

lua> logb(123) + 1 -- bits of 123
7

Update:
base(n, b) extended to negative n's. It uses Lua floor-mod property. (sign matching divisor)
With this update, we have invariant: horner(base(n, b), b) = n

lua> pprint(base(-123, -2)) -- negative b, always non-negative digits
{ 1, 0, 0, 0, 0, 1, 0, 1 }
lua> pprint(base(-123, +2)) -- positive b, sign of digits = sign of n
{ -1, -1, -1, -1, 0, -1, -1 }