Number Trick

[coderJeff]

@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 answer
end function

function 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 answer
end function

function 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 true
end function

function 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 result
end function

dim bits as string = chr( 3, 255, 7, 99 )
dim point_5 as string = ""

print "step                             bits   'point_5'                       "
print "---- -------------------------------- . --------------------------------"

dim count as integer = 0

'' halfing
do
   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 += 1
loop

print "---- -------------------------------- . --------------------------------"

'' doubling
do
   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 )
loop

sleep


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]

@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 .5 to l_avg
add half larger number to r_avg

etc....

[coderJeff]

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 1
function 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 answer
end 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 1
function 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 answer
end function


[coderJeff]

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

Don't get ahead of yourself.
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]

@CoderJeff

Your the GOD!!

Thanks for the code , i got it working..

I'll post the multiplier tomorrow... Time for bed... it's 9 o-clock..

[albert]

@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 1
function 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 answer
end 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 1
function 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 answer
end 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."
    sleep

loop until inkey = chr( 27 )

sleep
end



[coderJeff]

And it also sometimes compresses a few bits..

Stay focused. It's not compression. Something else is happening. Some information is actually hidden somewhere else. It's a very small detail, but important.