Bits of integer

12052022, 12:12 PM
(This post was last modified: 12052022 01:03 PM by Albert Chan.)
Post: #1




Bits of integer
This was a PM that I thought wothy of starting a thread: Number of Bits in a Integer
Albert Chan Wrote:Unless you have correct implementation of log2 (or binary logb), do this instead: It seems it is harder than it look, even with "perfect" log2 >20 def FNB(N) = IP(LOG2(N))+1 >X = 2^35 >X, FNB(X1), FNB(X), FNB(X+1) 34359738368 36 36 36 For binary machine, code is trivial, bit_length(x) = logb(x) + 1 For decimal machine, we may be hit with rounding errors. Any ideas ? 

12052022, 12:41 PM
(This post was last modified: 12052022 01:07 PM by Werner.)
Post: #2




RE: Bits of integer
Hi, Albert!
Yes, the method I used in the VA12c challenge will return the correct answer in linear time for all arguments up to 2^351 (on a 42S) or to 2^WSIZE1 on Free42 (WSIZE<45): Code: LBL D Sadly, that cannot be used on the 41. Don't know about the 71. On the 48, something similar may be done: Code: \<< BIN R\>B \>STR SIZE 3.  \>> Cheers, Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

12052022, 02:55 PM
(This post was last modified: 12052022 03:34 PM by JF Garnier.)
Post: #3




RE: Bits of integer
(12052022 12:12 PM)Albert Chan Wrote: >20 def FNB(N) = IP(LOG2(N))+1 The same occurs with LOG10 when trying to get the exponent of a number: X=10^11 LOG10(X);LOG10(X1) 11 11 Fortunately, in this case we have the EXPONENT() function. (12052022 12:41 PM)Werner Wrote: Yes, the method I used in the VA12c challenge will return the correct answer in linear time for all arguments up to 2^351 (on a 42S) or to 2^WSIZE1 on Free42 (WSIZE<45): On the 71B or 75C w/ Math ROM, you can do: DEF FNB(X)=LEN(BSTR$(X,2)) but I find it quite inelegant to resort to string conversion. Edit: removed my other proposal. made a mistake in my tests :( JF 

12052022, 04:13 PM
Post: #4




RE: Bits of integer
(12052022 02:55 PM)JF Garnier Wrote: On the 71B or 75C w/ Math ROM, you can do: >10 DEF FNB(X)=LEN(BSTR$(X,2)) >X = 2^39 >X 549755813888 >FNB(X1), FNB(X) 39 40 >Y$ = BSTR$(X,2) ERR:String Ovfl FNB(x) work, but intermediate values cannot be stored. Will the "overflowed" intermediate wreck havoc ? 

12052022, 04:29 PM
Post: #5




RE: Bits of integer
(12052022 04:13 PM)Albert Chan Wrote: >10 DEF FNB(X)=LEN(BSTR$(X,2)) You got Overflow because by default undimensioned string variables are limited to 32 characters. Simply execute DIM Y$[40] and the assignment will work. BSTR$ will never produce a string longer than 40 chars because its argument must be < 999,999,999,999.5 V. All My Articles & other Materials here: Valentin Albillo's HP Collection 

12052022, 10:06 PM
(This post was last modified: 12062022 02:50 AM by robve.)
Post: #6




RE: Bits of integer
(12052022 12:12 PM)Albert Chan Wrote: This was a PM that I thought wothy of starting a thread: Number of Bits in a Integer For C (and lua etc) I came up with a simple binary search to find the position of the leading bit in a 32 bit integer in 5 search steps: Code: unsigned int n, k, v = <number>; It's fast in C, since the compiled code operates with a few registers using bitwise operations. But on the HP71B we will need to shift with integer division and integer multiplication. Forth has shift words. Another trick is to normalize the integer to a clean form before taking the log2, similar to this: Code: x = (x >> 1); As a side note, the LZCNT CPU instruction counts leading zeros and can be used in e.g. C/C++ with __builtin_clz(). The POPCNT CPU instruction counts the number of nonzero bits. That neither work with a HP71B of course.  Rob "I count on old friends to remain rational" 

12062022, 12:15 AM
Post: #7




RE: Bits of integer
Hi, robve
We can do binary searches without the costly integer division. lua> bisect = require'primepi'.bisect lua> pow2 = {} lua> for i=1,52 do pow2[i] = 2^i end lua> function bits(n) return bisect(pow2, n) end lua> for n = 1, 9 do print(n, bits(n)) end 1 1 2 2 3 2 4 3 5 3 6 3 7 3 8 4 9 4 It would be nice if HP71B has builtin binary search code. Getting it right is hard. Are you one of the 10% of programmers who can write a binary search? Binary Search and Exclusive Upper Bounds 

12062022, 07:41 AM
Post: #8




RE: Bits of integer
(12062022 12:15 AM)Albert Chan Wrote: Getting it right is hard. Even Java had its problem with it: 

12062022, 08:29 AM
Post: #9




RE: Bits of integer  
12062022, 06:49 PM
(This post was last modified: 12122022 10:35 PM by Albert Chan.)
Post: #10




RE: Bits of integer
All codes (sorted from slowest to fastest) produced a sum of 388874.
All codes were run combined with below test codes. Test Code Wrote:10 DESTROY ALL @ RANDOMIZE 1 @ T=0 @ SETTIME 0 General binary search function turns out much slower, perhaps due to cost of array lookup. But, binary search code might be useful for other applications, so I post it here. Below, all timings done on Emu71/DOS WinXP (~ 200X speed) Note: H=N+1 is an exclusive upper bound Time = 18.6 seconds Wrote:15 N=39 @ DIM A(N) @ X=1 @ FOR I=1 TO N @ X=X+X @ A(I)=X @ NEXT I With inclusive upper bound, binary search code look like this: Code: 100 DEF FNB(X) @ L=1 @ H=N Avoiding array lookup, even with slow DIV, binary search is faster. Time = 9.97 seconds Wrote:100 DEF FNB(X) @ B=1 Hardcoded binary search without DIV is possible, but messy, with many branches. To give an idea of timing, I did a linear search for hex digit, then zeroin to bits. Time = 8.25 seconds Wrote:100 DEF FNB(X) @ SELECT X JF Garnier code, limit size of LOG2 argument. Time = 7.72 seconds Wrote:100 DEF FNB(X) JF Garnier code, binary string length, fastest of them all! Thanks! Time = 5.81 seconds Wrote:100 DEF FNB(N)=LEN(BSTR$(N,2)) 

12062022, 07:15 PM
Post: #11




RE: Bits of integer
(12052022 10:06 PM)robve Wrote: For C (and lua etc) I came up with a simple binary search to find the position of the leading bit in a 32 bit integer in 5 search steps: This is similar to Joe Horn's program from 1Minute Marvels: Code:


12062022, 07:26 PM
Post: #12




RE: Bits of integer
(12062022 06:49 PM)Albert Chan Wrote: All codes (sorted from slowest to fastest) produced a sum of 388874. Very nice. But you can avoid divisions (right shifts) solely by using multiplications (left shifts). Do you see what I mean and how to do that? Also, in general, to find the leading bit in a nbit binary number is asymptotically faster with binary search taking O(log(n)) asymptotic execution time as opposed to producing a string of 1 to n bits, which takes O(n) time. The (im)practical aspects of the HP71B makes binary search slow. Its BASIC is not suitable for this approach, especially when using costly divisions. Using hard coded branches and complicated expressions isn't helping performance either. (12062022 12:15 AM)Albert Chan Wrote: Hi, robve The bitshift binary search has no issues with edge cases, since we're dealing with integers of 32 bit (or 8, 16, 32, 64 bit for that matter, with a tweak to the code): 1: 0 2: 1 3: 1 4: 2 5: 2 6: 2 7: 2 8: 3 9: 3 10: 3 11: 3 12: 3 13: 3 14: 3 15: 3 16: 4 17: 4 ... 511: 8 512: 9 ... 4294967292: 31 4294967293: 31 4294967294: 31 4294967295: 31 Sure works like a charm. I like it because the underlying machine code is simple and efficient.  Rob "I count on old friends to remain rational" 

12062022, 08:15 PM
Post: #13




RE: Bits of integer
Here is a cryptic "one liner" in C for binary search with left shifts and a right shift by one bit (for division by two):
unsigned int k, n, u, v, w = <number>; for (k = 16, n = 0, v = 1, u = v << k; k; k >>= 1, u = v << k) if (w >= u) { n += k; v = u; } or how about the same with multiplications and square roots, in case shifts aren't permitted: unsigned int k, n, s, u, v, w = <number>; for (k = 16, n = 0, v = 1, u = s = 65536; k; k /= 2, s = sqrt(s), u = v * s) if (w >= u) { n += k; v = u; } The square roots are simply 65536, 256, 16, 4, 2, so can be precomputed or put in an unrolled loop: n = 0; v = 1; u = 65536; if (w >= u) { n = 16; v = u; } u = v * 256; if (w >= u) { n += 8; v = u; } u = v * 16; if (w >= u) { n += 4; v = u; } u = v * 4; if (w >= u) { n += 2; v = u; } u = v * 2; if (w >= u) { n += 1; } Add a step to extend to 64 bit numbers or a few more steps to go very far beyond if your machine can handle it.  Rob "I count on old friends to remain rational" 

12062022, 09:34 PM
Post: #14




RE: Bits of integer
(12062022 07:26 PM)robve Wrote: Very nice. But you can avoid divisions (right shifts) solely by using multiplications (left shifts). Yes, it can be done this way too. The problem is, for HP71B, *both* multiply and divide are costly. Divide a bit worse, but it is in the same ballpark. Programming in interpreted BASIC is very different than compiled languages. Also, powof2 and powof10 numbers never match (except for 2^0 = 10^0 = 1) This required an extra step to correct for the boundary. (bolded line) Below could optimize a bit, but likely still slower than binary search with DIV (9.97 seconds) Time = 11.55 seconds Wrote:10 DESTROY ALL @ RANDOMIZE 1 @ T=0 @ SETTIME 0 

12072022, 12:52 AM
Post: #15




RE: Bits of integer
Is there not a (short) way to do this with an HP16C, or with any other calculator with a similar or "better" (DM / WP) instruction set?
("better" → for binary computations) Bruno Sanyo CZ0124 ⋅ TI57 ⋅ HP15C ⋅ Canon X07 + XP140 Monitor Card ⋅ HP41CX ⋅ HP28S ⋅ HP50G ⋅ HP50G 

12072022, 06:33 AM
Post: #16




RE: Bits of integer
Log₂ is the way here.
The 34S included this function. The DM43/WP43/C43 will, likely, also include it. Pauli 

12072022, 07:18 AM
(This post was last modified: 12072022 07:27 AM by Joe Horn.)
Post: #17




RE: Bits of integer
Just for fun, here's my RPL solution which appeared first as a "How Does This Work" challenge many years ago. It also was included in Richard Nelson's "One Minute Marvels" collection.
Input: N as an Integertype object, any size. Output: Length of binary version of N. << 0 1 ROT FOR SWAP 1 + SWAP STEP >> Not fast, but accurate, and different. <0ɸ0> Joe 

12072022, 08:00 AM
Post: #18




RE: Bits of integer
Of course, calling the local variable 'SWAP' is meant to confuse the uninitiated!
But a marvel it is, indeed. Cheers, Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

12072022, 08:41 AM
Post: #19




RE: Bits of integer
(12072022 06:33 AM)Paul Dale Wrote: Log₂ is the way here. As noted in the OP, the log2 method can fail when the argument is close to the maximum representable integer. As does log10 fail to extract the number's exponent on various machines in the same condition: HP41C, HP15C: 1E9 1  LOG INT > 9 Free42: 1E33 1  LOG IP > 33 It's just a rounding effect (correct results, no error). But I agree that, in most cases when the argument range is known and limited, the log2 method is the simplest (but not necessary the fastest) way. JF 

12072022, 02:51 PM
Post: #20




RE: Bits of integer
(12072022 08:41 AM)JF Garnier Wrote: But I agree that, in most cases when the argument range is known and limited, the log2 method is the simplest log2(2^n ± x) = n + log2(1 ± x/2^n) ≈ n ± x/2^n/ln(2) For 12 decimal digits, n <= 39 If last term is going to be round off, last term less than 0.5E10 x/2^n/ln(2) < 0.5E10 2^n/x > 0.839759 * 2^35 If x=1, we have n >= 35 If n=39, we have x < 2^4/0.839759 <= 19 >C=2^35 >LOG2(C2),LOG2(C1), LOG2(C+1), LOG2(C+2) 34.9999999999 35 35 35.0000000001 >C=2^39 >LOG2(C20), LOG2(C19), LOG2(C+19), LOG2(C+20) 38.9999999999 39 39 39.0000000001 The 2 numbers in the middle get rounded to integer, as expected. > bits(x) = IP(LOG2(x))+1 only work upto 2^35  2 = 34,359,738,366 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)