[PUZZLE] Binary-to-decimal Golf Challenge (fixed; please retry)
Phil Pilgrim (PhiPi)
Posts: 23,514
A couple recent threads,
got me thinking about the quickest way to convert a 32-bit binary value to decimal in PASM. This makes for an interesting (to me anyway) golf challenge. So I created a framework for a contest to see who can come up with the quickest PASM program to take a 32-bit long and convert it to ten decimal ASCII digits, including leading zeroes. Here's the program framework, into which I've embedded my own entry:
Here are my results:
Obviously, I could have unrolled the loop for even more savings, but the program would have grown too large to be practical. Anyway, recognition will be given for minimizing the worst and average values. Please use the framework attached for the fairest comparisons.
Good luck!
-Phil
got me thinking about the quickest way to convert a 32-bit binary value to decimal in PASM. This makes for an interesting (to me anyway) golf challenge. So I created a framework for a contest to see who can come up with the quickest PASM program to take a 32-bit long and convert it to ten decimal ASCII digits, including leading zeroes. Here's the program framework, into which I've embedded my own entry:
{{
***************** bin2dec Golf Challenge *******************
DO NOT MODIFY ANY SPIN CODE,
except _clkmode and/or _xinfreq, if needed for your platform.
}}
CON
_clkmode = xtal1 + pll16x
_xinfreq = 5_000_000
OBJ
pst : "Parallax Serial Terminal"
num : "Simple_Numbers"
VAR
long state, binary, time
byte decimal[11]
PUB start | seed, value, best, worst, sum, n
cognew(@bin2dec, @binary)
pst.start(9600)
pst.str(string("bin2dec code size: "))
pst.dec((@end_code - @begin_code + @end_var - @begin_var) >> 2)
pst.str(string(" longs", 13))
n~
sum~
best := $7fff_ffff
worst~
repeat 1000
seed := rand(seed)
value := seed
repeat while value
binary := value
repeat while binary
if (dec2bin(@decimal) == value)
best <#= time
worst #>= time
sum += time
n++
else
pst.str(string("Error", 13, 13, "Input = "))
pst.str(num.decx((value >> 1) / 50_000, 5))
pst.str(num.decx((((value >> 1) // 50_000) << 1) | value & 1, 5))
pst.str(string(13, "Output = "))
pst.str(@decimal)
'repeat
value >>= 4
pst.str(string("Success after "))
pst.dec(n)
pst.str(string(" tests.", 13, "Number of instructions needed per conversion:", 13, " Best: "))
pst.dec(best >> 2)
pst.str(string(13, " Worst: "))
pst.dec(worst >> 2)
pst.str(string(13, " Avg: "))
pst.dec((sum / n) >> 2)
PUB rand(r)
case state++
0: return 4_199_999_999
1: return 3_999_999_999
other: return ?r
PUB dec2bin(str_addr)
repeat 10
result := result * 10 + byte[str_addr++] - "0"
DAT
bin2dec mov time_addr,par 'DO NOT MODIFY.
add time_addr,#4 'DO NOT MODIFY.
mov dec_addr,par 'DO NOT MODIFY.
add dec_addr,#8 'DO NOT MODIFY.
main_lp rdlong x,par wz 'DO NOT MODIFY.
if_z jmp #main_lp 'DO NOT MODIFY.
neg timer,cnt 'DO NOT MODIFY.
begin_code 'DO NOT MODIFY.
'-------[Begin Your Golf Code]-------------------------------------------------
'
' Upon entry, x contains a 32-bit binary value, and
' dec_addr contains the hub address of the first byte of the result string.
' Your golf code must write ten ASCII digits to the result string.
movs :ld_comp,#second_comp 'Number is less than 8 billion, so start with 4 billion.
mov comp,first_comp
mov ndigits,#10 'Do ten digits.
mov digit_addr,dec_addr 'Initialize digits hub pointer.
mov digit,#"0" 'Initialize first digit.
jmp #:start 'Jump into compar routine for "4".
:digit_lp mov digit,#"0" 'Initialize next digit.
cmpsub x,comp wc 'Is most-significant digit at least 8?
if_c add digit,#8 ' Yes: Add 8.
shr comp,#1 'Divide compare value by 2.
:start cmpsub x,comp wc 'Is most-significant digit at least 4?
if_c add digit,#4 ' Yes: Add 4.
shr comp,#1 'Divide compare value by 2.
cmpsub x,comp wc 'Is most-significant digit at least 2?
if_c add digit,#2 ' Yes: Add 2.
shr comp,#1 'Divide compare value by 2.
cmpsub x,comp wc 'Is most-significant digit at least 1?
if_c add digit,#1 ' Yes: Add 1.
wrbyte digit,digit_addr 'Write the digit to the string.
add digit_addr,#1 'Increment digit pointer.
:ld_comp mov comp,0-0 'Get next compare value.
add :ld_comp,#1 'Increment to point to next compare value.
djnz ndigits,#:digit_lp 'Go back for next digit.
'-------[End Your Golf Code]---------------------------------------------------
end_code add timer,cnt 'DO NOT MODIFY.
wrlong timer,time_addr 'DO NOT MODIFY.
mov x,#0 'DO NOT MODIFY.
wrlong x,par 'DO NOT MODIFY.
jmp #main_lp 'DO NOT MODIFY.
begin_var 'DO NOT MODIFY.
'-------[Begin Your Golf Variables]--------------------------------------------
first_comp long 4_000_000_000 'Initial digit compare values.
second_comp long 0_800_000_000
long 0_080_000_000
long 0_008_000_000
long 0_000_800_000
long 0_000_080_000
long 0_000_008_000
long 0_000_000_800
long 0_000_000_080
long 0_000_000_008
digit res 1
comp res 1
ndigits res 1
digit_addr res 1
'-------[End Your Golf Variables]----------------------------------------------
end_var 'DO NOT MODIFY.
x res 1 'DO NOT MODIFY.
dec_addr res 1 'DO NOT MODIFY.
time_addr res 1 'DO NOT MODIFY.
timer res 1 'DO NOT MODIFY.
Here are my results:
bin2dec code size: 33 longs Success after 7916 tests. Number of instructions needed per conversion: Best: 204 Worst: 204 Avg: 204
Obviously, I could have unrolled the loop for even more savings, but the program would have grown too large to be practical. Anyway, recognition will be given for minimizing the worst and average values. Please use the framework attached for the fairest comparisons.
Good luck!
-Phil
Comments
Phil's Golf Challenge
Success after 8000 tests.
Number of instructions needed per conversion:
Best: 135
Worst: 243
Avg: 184
(Phil's 204, 204, 204)
I used Phil's code as the base, and kept the labels the same where possible.
You will note the changes that I had to do...
1. remove the local labels (i.e. remove the ":")
2. add a delay when the program starts, plus a message "Phil's Golf Challenge".
3. I use 6.5MHz xtal but the results will be the same since we are counting clock cycles.
Don't peek if you are attempting the challenge
bin2dec_golf_cluso[1].spin
BTW, is anyone here familiar with the "double dabble" algorithm? It's the gold standard for converting binary to BCD in hardware logic, gate arrays, etc. But a quick perusal left me with the impression that it would not be efficient to implement on the Propeller.
-Phil
I may have a go over the w/e, Think it will use quite a bit of code though.
In real life, the program could be sped up by finding the first significant bit, because the expectation would be that the number would likley not be random, and hence more often much less than 10 significant digits.
My programming on minis was on a computer that was fully decimal... Yes, memory was decimal, and so were the instructions, so a multiply was 1-10 digits by 1-10 digits (both in decimal) and the result was stored in the B operand for a length of a+b so no overflow was possible. Caveat was to ensure the B had a length reserved of a+b. Division was the reverse. Even the instructions were 10 bytes!
My programming in micros never really dealt with large numbers. Just lots of interfacing, comms protocol conversions, modems, etc.
I made a slight improvement to your original code. If the digit is 8, then it skips down to test for 1 since the digit cannot be larger than 9.
I get a best of 192, worst of 204, and avg of 200.
I had tried the double dabble awhile back, took too much code and was not faster on the propeller.
movs :ld_comp,#second_comp 'Number is less than 8 billion, so start with 4 billion. mov comp,first_comp mov ndigits,#10 'Do ten digits. mov digit_addr,dec_addr 'Initialize digits hub pointer. mov digit,#"0" 'Initialize first digit. jmp #:start 'Jump into compar routine for "4". :digit_lp mov digit,#"0" 'Initialize next digit. cmpsub x,comp wc 'Is most-significant digit at least 8? if_c add digit,#8 ' Yes: Add 8. if_c shr comp,#3 ' [TH] If digit was 8, skip to test for 1 (can't be 4 or 2) if_c jmp #:digit_1 shr comp,#1 'Divide compare value by 2. :start cmpsub x,comp wc 'Is most-significant digit at least 4? if_c add digit,#4 ' Yes: Add 4. shr comp,#1 'Divide compare value by 2. cmpsub x,comp wc 'Is most-significant digit at least 2? if_c add digit,#2 ' Yes: Add 2. shr comp,#1 'Divide compare value by 2. :digit_1 cmpsub x,comp wc 'Is most-significant digit at least 1? if_c add digit,#1 ' Yes: Add 1. wrbyte digit,digit_addr 'Write the digit to the string. add digit_addr,#1 'Increment digit pointer. :ld_comp mov comp,0-0 'Get next compare value. add :ld_comp,#1 'Increment to point to next compare value. djnz ndigits,#:digit_lp 'Go back for next digit.Bean[EDIT] With new version I get Best=168, Worst=204, Avg=200
This is only 17 instructions + 2 longs of data.
Timing is best=146, worst=306, avg=214
mov ndigits,#10 'Do ten digits. mov digit_addr,dec_addr 'Initialize digits hub pointer. mov digit,#"0" :first_digit cmpsub x,first_comp wc, wr ' Do first digit as special case if_c add digit,#1 if_c jmp #:first_digit :next_digit wrbyte digit,digit_addr 'Write the digit to the string. add digit_addr,#1 'Increment digit pointer. mov digit,#"0" :next_digit_loop cmpsub x,second_comp wc, wr if_c add digit,#1 if_c jmp #:next_digit_loop mov comp,x 'x = x * 10 shl x,#2 add x,comp shl x,#1 djnz ndigits,#:next_digit 'Go back for next digit. '-------[End Your Golf Code]--------------------------------------------------- add timer,cnt 'DO NOT MODIFY. wrlong timer,time_addr 'DO NOT MODIFY. mov x,#0 'DO NOT MODIFY. wrlong x,par 'DO NOT MODIFY. jmp #:main_lp 'DO NOT MODIFY. '-------[Begin Your Golf Variables]-------------------------------------------- first_comp long 1_000_000_000 'Initial digit compare values. second_comp long 0_100_000_000Bean[EDIT] New version gives Best=134, Worst=390. Avg=206
'Two good contributions! Your second one gives me an idea ...
-Phil
Phil's Golf Challenge
Success after 8000 tests.
Number of instructions needed per conversion:
Best: 135
Worst: 243
Avg: 184
plus Bean's 8 cannot be 4 or 2:
Phil's Golf Challenge
Success after 8000 tests.
Number of instructions needed per conversion:
Best: 135
Worst: 219
Avg: 176
'-------[Cluso's Golf Code]------------------------------------------------- movs next_digit,#comp1 ' setup msd comparison mov ndigits,#10 'Do ten digits. mov digit_addr,dec_addr 'Initialize digits hub pointer. mov digit,#"0" 'Initialize first digit. mov comp,comp1 ' start msd (first digit) cmpsub x,comp wc,nr ' digit > 0 ? if_nc jmp #skip_digit ' n: then this digit =0 shl comp,#2 ' make it a "4" jmp #first_time next_digit mov comp,0-0 'Get next compare value. mov digit,#"0" 'Initialize next digit. cmpsub x,comp wc,nr ' digit > 0 ? if_nc jmp #skip_digit ' n: then this digit =0 shl comp,#3 ' make it an "8" cmpsub x,comp wc 'Is most-significant digit at least 8? if_c add digit,#8 ' Yes: Add 8. if_c shr comp,#3 ' if 8, cannot be 4 or 2, so go straight to 1 if_c jmp #digit_1 ' (thanks Bean) shr comp,#1 'Divide compare value by 2. first_time cmpsub x,comp wc 'Is most-significant digit at least 4? if_c add digit,#4 ' Yes: Add 4. shr comp,#1 'Divide compare value by 2. cmpsub x,comp wc 'Is most-significant digit at least 2? if_c add digit,#2 ' Yes: Add 2. shr comp,#1 'Divide compare value by 2. digit_1 cmpsub x,comp wc 'Is most-significant digit at least 1? if_c add digit,#1 ' Yes: Add 1. skip_digit wrbyte digit,digit_addr 'Write the digit to the string. add digit_addr,#1 'Increment digit pointer. add next_digit,#1 ' setup for next msd comparison djnz ndigits,#next_digit 'Go back for next digit.bin2dec_golf_cluso[2].spin
That is quite a remarkable improvement.
Glad I could help
Bean
Excellent! This is what I like about "crowd-sourcing": there's always a better way!
-Phil
DAT org 0 asm_entry mov temp,par ' get 32bit binary mov mystring,allzero 'reset to allow repeats mov mystring+1,allzero 'reset to allow repeats mov mystring+2,allzero+1 'reset to allow repeats movs keepsub,#highval 'reset to allow repeats movd strpnt,#mystring 'reset to allow repeats mov loopcnt,#10 keepsub cmpsub temp,0-0 wc strpnt if_c add 0-0,nibble if_c jmp #keepsub ror nibble, #8 wc if_c add strpnt, my512 add keepsub,#1 djnz loopcnt, #keepsub jmp $ ' result: a zero terminated byte ascii string at mystring highval long 1000000_000,100000_000,10000_000,1000_000,100_000,10_000,1_000,100,10,1 allzero long $30303030, $30300000 nibble long 1<<24 my512 long 1<<9 loopcnt res 1 mystring res 3 temp res 1'Looks intriguing. Format it for the framework, and see if it works. (Otherwise, it doesn't count.
-Phil
I also tried 4,2,2,1 and no luck either.
This is my best so far, although I can get less spread results such as 163,179,172
Phil's Golf Challenge
Success after 8000 tests.
Number of instructions needed per conversion:
Best: 131
Worst: 199
Avg: 156
movs next_digit,#comp1 ' setup msd comparison mov ndigits,#10 'Do ten digits. mov digit_addr,dec_addr 'Initialize digits hub pointer. mov digit,#"0" 'Initialize first digit. mov comp,comp1 ' start msd (first digit) cmpsub x,comp0 wc,nr ' digit > 0 ? if_nc jmp #skip_digit ' n: then this digit =0 jmp #first_time next_digit mov comp,0-0 'Get next compare value. mov digit,#"0" 'Initialize next digit. cmpsub x,comp wc ' at least 2? if_nc jmp #digit_1 if_c add digit,#2 ' y: +2 cmpsub x,comp wc ' at least 2? if_nc jmp #digit_1 if_c add digit,#2 ' y: +2 first_time cmpsub x,comp wc ' at least 2? ' if_nc jmp #digit_1 'makes worse if_c add digit,#2 ' y: +2 cmpsub x,comp wc ' at least 2? if_c add digit,#2 ' y: +2 digit_1 shr comp,#1 ' divide by 2 cmpsub x,comp wc ' at least 1? if_c add digit,#1 ' y: +1 skip_digit wrbyte digit,digit_addr 'Write the digit to the string. add digit_addr,#1 'Increment digit pointer. add next_digit,#1 ' setup for next msd comparison djnz ndigits,#next_digit 'Go back for next digit.bin2dec_golf_cluso[7].spin
Wow! That's a really nice (and surpising) result. I would not have guessed that 2,2,2,2,1 would beat 4,2,2,1.
-Phil
Yes, that is surprising. But I'm thinking it is because as soon as it fails any of the "2" tests, you can jump right to last "1" test.
Bean
a) Leading Zero suppression (Integer)
b) Leading Zero Suppression, with a user defined decimal point. The string would include a decimal point
eg "0.01234"
Sign is probably easiest managed outside the conversion, as well as units append.
Given the length is now more dynamic, a null append would let the caller manage this.
'All very good ideas for a finished product, but not part of the puzzle's core. You seem to like suggesting things for other people to do, but why not join the fun and contribute a solution of your own?
-Phil
-Phil
But I couldnt sleep last night so I was just mulling over the loop in my semi-sleep mode and added the instructions for the 22221 loop and they were shorter by a couple of instructions. With the extra jmp out to 1, that clinched the deal. Of course, the worst rose as the average shrunk. I did get a 163,179,172.
BTW I tried tony's solution but didn't get it to run. Maybe something I did, or something he left out. It certainly looks intriging with a lot of short loops.
Success after 8000 tests.
Number of instructions needed per conversion:
Best: 119
Worst: 119
Avg: 119
CogSaver
-Phil
probably not the most elegant solution, but it gets the job done.
I also noticed that the Hub access window comes into play for some potential
minor improvents when writing back the ASCII string.
File :
bin2dec_golf_V2.spin
The sequece of numbers generated seems to repeat itself, and higest digit
never goes above 1. (Hence the commented out lines in my program)
With the lines uncommented the timing jumps up to 87 instructions.
For reference the numbers that are generated is a repeat sequence of
CogSaver
and the code Size, including tables ?
Well spotted, seems a poor test pattern.
Given all code is using CMPSUB, I'll nominate values of 4199999999 and 3999999999 be added to the test values.
Anyway, a corrected version of the program now appears in the top post. It also reports the combined program and table size, but without including any res variables.
BTW, jmg, I'm still waiting to see an entry from you, since you seem so keenly interested in commenting on this thread.
-Phil
Why the focus on an entry from me ? - is competition entry now a condition of posting in the forum ?
- I do have an interest in Binary to Decimal, (and the logical practical extensions, of leading zero suppression, and decimal point handling) but I'll leave the finer code shuffling to the PASM experts.
My comment "Given all code is using CMPSUB, I'll nominate values of 4199999999 and 3999999999 be added to the test values" still stands, especially for those cases using jumps.
If you try to report a MAX, I'm surprised these values are not mandated in the tests ?
Basically I missed CogSaver's little trick with the last digit. Not sure that degree of unrolling is particularly good news on the Prop(!)
Thanks,
-Phil
Cool. How this matters, depends on the code.
If you look at #14, which uses jumps to skip adds, the MAX path on that is now number dependent, so it ideally needs tests for the most adds. (so least skips) - which may not always be a lot of 9's.
ie I think 9's are needed for #14, but for #9, it might be 7's - so perhaps such code should identify the worst-case-test value ?
For completeness i figured that I make an attempt at minimum codesize with the following result :
bin2dec_golfNewCS4.spin
CogSaver