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 }

[FLISZT]

(12-13-2022 02:37 AM)Joe Horn Wrote:  Here's a brute-force implementation of that method:

LBL A, 0, STO I, Rdn, LBL 0, g ISZ, f SR, g x≠0, GTO 0, RCL I, RTN

GSB A in any binary mode returns the number of bits needed to express X.

It works, but it's horrifically slow:
Input 2^40-1 outputs correct result of 40 in 15 seconds.
Input 2^40 outputs correct result of 41 in 15 seconds.

EDIT: 0 NOT with WSIZE of 64 returns 64 in 22 seconds.

That's not that much for a calculator that came out 40 years ago. My Sanyo (1977) needs more than 30s to compute the factorial of 69!!
I should have bought one 16C when you could find it in stores… Of course, with a DM16L, it would be faster (and it's about half the price).

(12-13-2022 09:17 AM)Joe Horn Wrote:  Here's a 16C-only routine that doesn't require any looping. The LJ command is on the [g] [A] key. #B is on the [g] [7] key.

LJ, 0, NOT, #B, x<>y, –

As before, put any value in X in any binary mode. The above routine returns the number of bits required to express X. If WSIZE is sufficiently large to put X on the stack, then this routine will always return the correct answer.

Inputs of 2^40-1 and 2^40 return the correct answers (40 and 41 respectively) in roughly 1.5 seconds, with a speed hit for a large WSIZE.

I have tried both of your programs at: https://stendec.io/ctb/rpn_prog.html
Thank you!

Too bad the RPL calculators don't have all the functions of the 16C. However, trying to program the missing functions might be a good exercise!