## Number Trick

General FreeBASIC programming questions.
coderJeff
Posts: 3342
Joined: Nov 04, 2005 14:23
Contact:

### Re: Number Trick

Stonemonkey wrote:@Albert

for divide by 2 you shift right by 1, bit 0 of the high byte gets shifted into bit 7 of the low byte.

Albert, you are getting ahead of yourself. Check that it works first.

Code: Select all

`function halfer( byref src as string, byref carry as ubyte = 0 ) as string   dim as string answer = string(len(src),0)   for i as integer = 0 to len( src ) - 1      answer[i] = (src[i] shr 1) + (carry and 1) shl 7      carry = src[i] and 1   next   return answerend functionfunction doubler( byref src as string, byref carry as ubyte = 0 ) as string   dim as string answer = string(len(src),0)   for i as integer = len( src ) - 1 to 0 step -1      answer[i] = (src[i] shl 1) + (carry and 1)      carry = src[i] shr 7   next   return answerend functionfunction isZero( byref src as const string ) as boolean   for i as integer = 0 to len( src ) - 1      if( src[i] ) then         return false      end if   next   return trueend functionfunction strToBin( byref src as const string ) as string   dim as string result = ""   for i as integer = 0 to len( src ) - 1      result &= bin( src[i], 8 )         next   return resultend functiondim bits as string = chr( 3, 255, 7, 99 )dim point_5 as string = ""print "step                             bits   'point_5'                       " print "---- -------------------------------- . --------------------------------"dim count as integer = 0'' halfingdo   print using "####"; count;   print " " & strToBin(bits) & " . " & point_5        '' quit if zero   if( isZero( bits ) ) then      exit do   end if      '' right most bit becomes the remainder   if( bits[len(bits)-1] and 1 ) then      point_5 = "1" + point_5   else      point_5 = "0" + point_5   end if             '' divide by 2   bits = halfer( bits )    count += 1loopprint "---- -------------------------------- . --------------------------------"'' doublingdo   print using "####"; count;   print " " & strToBin(bits) & " . " & point_5       count -= 1   '' quit if no more point_5   if( len(point_5) = 0 ) then      exit do   end if      '' divide by 2   if( left(point_5, 1) = "1" ) then      bits = doubler( bits, 1 )   else      bits = doubler( bits, 0 )   end if   '' remove a bit from point_5      point_5 = mid( point_5, 2 ) loopsleep`

There's lots of people here still willing to help. Maybe they will help explain. Sometimes hard to know what it is you are doing. Mixing strings of numbers and bits and characters. It's kind of all the same thing.
albert
Posts: 5916
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Number Trick

@CoderJeff

I'm working on character strings , each character being ASCII 0 to 255..

So:
If you have chr( 255 ) + chr( 255 ) and divide by 2 , you get chr( 127 ) + chr( 132 )

How do you double the chr( 127 ) + chr( 132 ) , to get chr( 255 ) + chr( 255 ) back ??

Your above code is so cryptic , i can't follow it.. It's worse than C++ , I skipped C++ , because it was to hard to follow.. I prefer Basic..

But I'm dividing down to zero , and then trying to rebuild the original chr() string with a doubler or adder... Which I'm still trying to figure out..

================================================================================================
I was originally trying to do a a multiplier , that uses averages to find the multiply result...
But discovered that dividing down to zero and making a binary map of the end fraction resulted in compression..
if you input 8 bytes and divide the characters down to "00000000" ( 8 zeros ) , you end up with a 30 to 40 bit fraction map...
you can use that fraction map to add a 1 to the doubler output when needed.. double + 1 or just double..
================================================================================================

After finding that the chr() string divided x 2 , down to zero , resulted in compression I spawned a new topic "Data Compression"
Where I'm working on the "Doubler" or "Adder"

My original post was to have two functions ( half and add )...
You put the smaller number on the left and the larger number on the right and extend it to the size needed for the answer..
Then you average each side and if the half ends in a .5 then you add .5 to the left and half the larger number to the right..
When the left average = the left number then the right average will equal the multiply result..

So you have
l_bot = smaller number
l_avg = 0
l_top = l_bot + l_bot

r_bot = larger number * first digit + zeros to make it as long as the answer
r_avg = 0
r_top = r_bot + r_bot

do
l_avg = l_bot + l_top / 2
r_avg = r_bot+r_top / 2

if l_avg ends in .5 then
add half larger number to r_avg

etc....
Last edited by albert on Sep 11, 2020 3:14, edited 1 time in total.
coderJeff
Posts: 3342
Joined: Nov 04, 2005 14:23
Contact:

### Re: Number Trick

You do need to know some things.
1) Bits of a byte 128, 64, 32, 16, 8, 4, 2, 1
2) Most significant is on the left, least significant on the right.

OK, here's the halfer and doubler same as above and can do 0 to 255 values, like in characters, just written another way. No weird bit shifting with SHL / SHR or masking with AND in this one.

Code: Select all

`'' source string is a sequence of characters, each 0 to 255'' we can optionally pass in a carry bit to start with'' we expect the carry to only ever be 0 or 1function halfer( byref src as string, byref carry as ubyte = 0 ) as string   '' initialize an empty answer string with zereos   '' same length as the source string   dim as string answer = string(len(src),0)   '' loop through each character   '' we must got from left to right assuming that   '' the most significant characters on the left   '' and the least significant characters on the right   '' we must go in this order because we are DIVIDING   '' and the carry bits have to go from HIGHER to LOWER    for i as integer = 0 to len( src ) - 1         '' divide the current character by 2      '' and add in the carry from the last one      '' the carry bit has to get added in to the      '' high bit of the current carracter      ''         if( carry = 1 ) then         answer[i] = (src[i] \ 2) + 128      else         answer[i] = (src[i] \ 2)                     end if      '' when dividing by 2, the lowest bit of      '' the character needs to get carried over      '' to the highest bit of the next character         ''      '' get the lowest bit of the character      ''      if( src[i] mod 2 = 1 ) then         carry = 1      else         carry = 0      end if   next   return answerend function'' source string is a sequence of characters, each 0 to 255'' we can optionally pass in a carry bit to start with'' we expect the carry to only ever be 0 or 1function doubler( byref src as string, byref carry as ubyte = 0 ) as string   '' initialize an empty answer string with zereos   '' same length as the source string   dim as string answer = string(len(src),0)   '' loop through each character   '' we must go from right to left assuming that   '' we must go in this order because we are DOUBLING   '' and the carry bits have to go from LOWER to HIGHER    for i as integer = len( src ) - 1 to 0 step -1         '' multiply the src character by 2 and add in      '' the carry.  we can simply add the carry      '' when we double the number, the lowest bit      '' is always 0, so we can simply add a 0 or 1      ''      answer[i] = src[i] * 2 + carry            '' the highest bit has to get carried to the      '' next higher character      ''            if( src[i] >= 128 ) then         carry = 1      else         carry = 0      end if    next   return answerend function`
coderJeff
Posts: 3342
Joined: Nov 04, 2005 14:23
Contact:

### Re: Number Trick

albert wrote:But discovered that dividing down to zero and making a binary map of the end fraction resulted in compression..

First, the modified halfer you made just doesn't do what you think.
Second, the "binary map" is just the same number, in binary. bits will be same order or reversed depending on how you put it together.

Take as much time as needed to focus on the smallest details of how this stuff works. If you get too far ahead and don't pay attention to the details, I predict I will be forced to suspend your account again.
albert
Posts: 5916
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Number Trick

@CoderJeff

Thanks for the code , i got it working..

I'll post the multiplier tomorrow... Time for bed... it's 9 o-clock..
albert
Posts: 5916
Joined: Sep 28, 2006 2:41
Location: California, USA

### Re: Number Trick

@CoderJeff

Your code works... And it also sometimes compresses a few bits.. With 10 bytes input , it sometimes outputs 9.35 to 9.75 bytes...

But the important part is , the output matches the input...

Code: Select all

`screen 19'' source string is a sequence of characters, each 0 to 255'' we can optionally pass in a carry bit to start with'' we expect the carry to only ever be 0 or 1function halfer( byref src as string, byref carry as ubyte = 0 ) as string   '' initialize an empty answer string with zereos   '' same length as the source string   dim as string answer = string(len(src),0)   '' loop through each character   '' we must got from left to right assuming that   '' the most significant characters on the left   '' and the least significant characters on the right   '' we must go in this order because we are DIVIDING   '' and the carry bits have to go from HIGHER to LOWER   for i as integer = 0 to len( src ) - 1         '' divide the current character by 2      '' and add in the carry from the last one      '' the carry bit has to get added in to the      '' high bit of the current carracter      ''         if( carry = 1 ) then         answer[i] = (src[i] \ 2) + 128      else         answer[i] = (src[i] \ 2)                     end if      '' when dividing by 2, the lowest bit of      '' the character needs to get carried over      '' to the highest bit of the next character         ''      '' get the lowest bit of the character      ''      if( src[i] mod 2 = 1 ) then         carry = 1      else         carry = 0      end if   next   return answerend function'' source string is a sequence of characters, each 0 to 255'' we can optionally pass in a carry bit to start with'' we expect the carry to only ever be 0 or 1function doubler( byref src as string, byref carry as ubyte = 0 ) as string   '' initialize an empty answer string with zereos   '' same length as the source string   dim as string answer = string(len(src),0)   '' loop through each character   '' we must go from right to left assuming that   '' we must go in this order because we are DOUBLING   '' and the carry bits have to go from LOWER to HIGHER   for i as integer = len( src ) - 1 to 0 step -1         '' multiply the src character by 2 and add in      '' the carry.  we can simply add the carry      '' when we double the number, the lowest bit      '' is always 0, so we can simply add a 0 or 1      ''      answer[i] = src[i] * 2 + carry            '' the highest bit has to get carried to the      '' next higher character      ''            if( src[i] and 128 ) then         carry = 1      else         carry = 0      end if   next   return answerend function'===================='Test Functions'====================do    randomize    dim as string s = space( 10 )    for a as longint = 1 to len( s ) step 1        s[ a - 1 ] = int( rnd * 256 )    next        dim as string original = s    dim as string compare = string( len( s ) , chr( 0 ) )    dim as longint length = len( s )    dim as string point_5 = ""    dim as longint ctr = 0        dim as double time1 , time2    time1 = timer    do                ctr+= 1                'Make a binary map of all the times the division results in .5 or 0        if asc( right( s , 1 ) ) mod 2 = 1 then point_5 += "1" else point_5+= "0"                print        print ctr ;"  ";         for a as longint = 1 to len( s )            print asc( mid( s , a , 1 ) ) ; " " ;         next        print                s = halfer( s )                'sleep 500                if inkey = chr( 27 ) then exit do            loop until s = compare    time2 = timer        dim as string answer = s    for a as longint = len( point_5 ) to 1 step - 1        answer = doubler( answer , val( mid( point_5 , a , 1 ) ) )    next        print    print "Input   = " ;  original    print "Output =  "; answer        print    print "Div Map = " ; len( point_5 ) ; " Bits  " ; point_5    print    print "Input bytes = " ; length    print "Output bytes = " ; len( point_5 ) / 8    print    print "Compression ratio  "; 100 - ( 100 / ( length / ( len(point_5 ) / 8 ) ) ) ; "%"     print    print "Time to compress = " ; time2 - time1    print    print "Press a key for next set."    sleeploop until inkey = chr( 27 )sleepend`
coderJeff
Posts: 3342
Joined: Nov 04, 2005 14:23