Squares

General FreeBASIC programming questions.
Locked
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Dodicat

Is there a way to get compression out of your remainders code???

========================================================
I did my program a little different...

Now you adjust the values upwards by 1 until you get an output.. If the mods don't have an equal , it just outputs nothing..
If the mods equal the output then it prints out the various values that equal up to the input...

If it gets 255 correct it will get all lower bytes okay as well..

Code: Select all


screen 19

dim as longint v , v1 , v2 , v3 , v4
dim as longint  md1 , md2 , md3 , md4
do
            
            do
                'ADJUST 4 , 9 , 12 TO DIFFERENT VALUES , HAS TO BE 3 OR GREATER
                md1 = int( rnd * 4 )
                md2 = int( rnd * 9 )
                md3 = int( rnd * 12 )
                
            loop until md1 > 1 and md2 > 1 and md3 > 1
            
            'randomize
            v = 255 'int( rnd * 256 )
            
            v1 = v mod md1
            v2 = v mod md2
            v3 = v mod md3
            
            dim as longint s , s1 , s2 , s3 , s4 , value
            for b as longint = 0 to 65536 step 1
                s = b
                s1 = s mod md1
                s2 = s mod md2
                s3 = s mod md3
                if s1 = v1 and s2 = v2 and s3 = v3 then value = b : exit for
            next
        
        if v = value then print v , value  , md1 , md2 , md3 : sleep
        
loop until inkey = chr( 27 )

sleep
end

I tried it with 65535... it outputs more than 16 bits at the smallest...

Every set that equals the input , add up to more bits than the input...
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

mod 3 , mod 8 , mod 11 , works with mod 3 , mod 7 , mod 13 as well..

Or mod 2 mod 11 mod 13...

They all add up to 9 bits... Back to the drawing board!!!!
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Squares

Post by dodicat »

To get a unique answer the mods must not be factors of each other and v should be less than the product of the mods.
Have a look at the mods here, I have set them bigger

Code: Select all

 
 

screen 19
Function HCF(a As Integer, b As Integer) As Integer
    If b=0 Then Return a Else Return HCF(b,a Mod b)
End Function

Function TestPairwiseCoprime(array() As Integer) As Integer
    For p1 As Integer  = Lbound(array) To Ubound(array) - 1
        For p2 As Integer  = p1 + 1 To Ubound(array)
            if array(p1)=1 or array(p2)=1 then return 0
            If HCF(array(p1),array(p2))<>1 then Return 0
        Next p2
    Next p1
    Return -1
End Function

Function Cremainder(coprimes() As Integer,remainders() As Integer) As longint
    #macro minv(a1,b1,ans)
    Scope
        Dim As longint a=a1,b=b1
        Dim As longint Cb=b,t,Div
        Dim As longint Starter = 0, Result = 1
        If (b=1) Then return 1
        While (a > 1)
            If b=0 Then Print "No can do":return 0
            Div = a\b
            t=b:b=a Mod b:a=t
            t=Starter:Starter=Result-Div*Starter:Result=t
        Wend
        If (Result<0) Then Result+=Cb
        ans=Result
    End Scope
    #endmacro
    Dim As longint p,Product =1,sum=0,ans
    For i as integer =Lbound(coprimes) To Ubound(coprimes):Product*=coprimes(i):Next
        For j as integer=Lbound(coprimes) To Ubound(coprimes)
            p=Product\coprimes(j)
            minv(p,coprimes(j),ans)
            sum+=remainders(j)*ans*p
        Next j
        Return sum Mod Product
    End Function
   
   
 
   
dim as longint v , v1 , v2 , v3 , v4
dim as longint  md1 , md2 , md3 , md4
dim as long t,m,n
do
           
            do
                'ADJUST 4 , 9 , 12 TO DIFFERENT VALUES , HAS TO BE 3 OR GREATER
                md1 = int( rnd * 100 ) '4
                md2 = int( rnd * 100 ) '9
                md3 = int( rnd * 100 ) '12
               dim as integer test(...)={md1,md2,md3}
               m=testpairwisecoprime(test()) 'ckeck none are factors of others.
               n=md1*md2*md3>255              'make sure the product is greater than 255
                t=md1 >= 1 and md2 >= 1 and md3 >= 1 and m and n
            loop until t
         
            
            v = int( rnd * 256 )
           
       
       
            v1 = v mod md1
            v2 = v mod md2
            v3 = v mod md3
            dim as integer remainders(1 to ...)={v1,v2,v3}
            dim as integer mods(1 to ...)={md1,md2,md3}
           
            dim as longint s , s1 , s2 , s3 , s4 , value
            for b as longint = 0 to v'65536 step 1
                s = b
                s1 = s mod md1
                s2 = s mod md2
                s3 = s mod md3
                if s1 = v1 and s2 = v2 and s3 = v3 then value = b : exit for
            next
       
       
           print "remainders:"
           print "v1","v2","v3"
           print v1,v2,v3
           print "mods:"
           print "md1","md2","md3"
           print md1,md2,md3
            var a= Cremainder(mods(),remainders())
            if a then print "Result = "; a;", (orig v = ";v;"),","(Albert's = ";value;")"
                for z as integer=lbound(remainders) to ubound(remainders)
        print a;" mod ";mods(z);" = ";remainders(z)
                next z
            print"_____________________"
            sleep
       
       
loop until inkey = chr( 27 )

sleep
end
 
 
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Dodicat

How would you write a program to find all the values for an altered binary???

Altered binary = 1 , 2 , 4 , 9 , 17 , 34 , 68 , 119 : adds up to 254..

I need to compare all the possible 256 combinations , so i can pick the correct values.
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Squares

Post by badidea »

Try 1,2,4,8,16,32,64,128
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@badidea

altered binary..

1 , 3 , 5 = 5 , 6 , 8 , 9 , there's no 7 , but 7 and 1 = 8 like 5 and 3...

1 , 3 , 5 , 7 you'd need a way to tell 5 , 3 from 7 , 1.... but they're both 2 bits.. so bit counting won't work.. so the next logical value would be 10

1 , 3 , 5 , 10 , then there's no 17 but 17 and 1 = 18 like 10 , 5 , 3

So you end up with 1 , 3 , 5 , 10 , 20 , 40 , 80 , 160...

A different set:
1, 2 , 5 , 9 ,18 , 36 , 72 ,144 , adds up to 287.. so it's 9 bits.. 32 greater than 255.. So the byte would roll over to 31....

So you need a way to tell 0 to 31 from 256 to 287..
=========================================

A different set: 1, 2 , 4 , 9 , 17 , 34 , 68 , 136 : adds up to 271 , 16 over 255 , so the byte would roll over to 0 to 15.
So you subtract 16 from each byte , then you add 16 back in the de-compressor...
angros47
Posts: 2321
Joined: Jun 21, 2005 19:04

Re: Squares

Post by angros47 »

@albert

Try your concept of altered binaries on number from 0 to 15 (all the numbers than can be expressed with one nibble). Then, write here the numbers, and the altered binary representation, so we can see if it would work or not
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@angros47

I was asking Dodicat , if he could write a program , to "compare" all the bits of an altered binary..

I was writing each set by hand, and it got too confusing...

1 , 2 , 4 , 9, 17 , 34 , 68 , 136

1 = 1

2 = 2
2 +1 = 3

4 = 4
4 + 1 = 5
4 + 2 = 6
4+ 2 +1 = 7

9 = 9
9 + 1 = 10
9 + 2 = 11
9 + 4 = 13
9 + 2 + 1 = 12
9 + 4 + 1 = 14
9 + 4 + 2 = 15
9 + 4 + 2 + 1 = 16

etc... It gets too confusing after 5 bits..

I need a program to do all the mundane stuff comparing the values... So i can play around with different sets..
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

You could do a 2 , 3 , 4 , 8

2 = 2

3 = 3
3 + 2 = 5

4 = 4
4 + 2 = 6
4 + 3 = 7
4 + 3 + 2 = 9

8 = 8
8 + 2 = 10
8 + 3 = 11
8 + 4 = 12
8 + 3 + 2 = 13
8 + 4 + 2 = 14
8 + 4 + 3 = 15
8 + 4 + 3 + 2 = 17

The next values , might be 16 , 32 ,64 , 128 like normal...

( !!~~ EDITED ~~!! )

I tried 2 , 3 , 4 , 8 , 16 , 32 , 64 , 128 and it doesn't compress... It expands..
Richard
Posts: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

Numbers = non-binary gender

Code: Select all

'====================================================
' Albert, put your choice of 8 numbers in this array
Dim As Short non_binary( 0 To 7 )= { 1 , 2 , 4 , 9, 17 , 34 , 68 , 136 }

'====================================================
' evaluate binary pattern
Dim As Short k, sum, freq( 0 To 255 )
For k = 0 To 255
    sum = 0
    If k And 1 Then sum += non_binary( 0 )
    If k And 2 Then sum += non_binary( 1 )
    If k And 4 Then sum += non_binary( 2 )
    If k And 8 Then sum += non_binary( 3 )
    If k And 16 Then sum += non_binary( 4 )
    If k And 32 Then sum += non_binary( 5 )
    If k And 64 Then sum += non_binary( 6 )
    If k And 128 Then sum += non_binary( 7 )
    if sum < 256 then freq( sum ) += 1    ' accumulate frequency distribution
Next k

'====================================================
' report any codes that are missing
For k = 0 To 255
    If freq( k ) = 0 Then Print k; " is missing."
Next k

'====================================================
Sleep
'====================================================
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

Thanks for the code..

But what about duplicates ?? like 1 , 5 , 6 ..Where you have 1 or more numbers , that equate to other combinations of numbers?
Richard
Posts: 3096
Joined: Jan 15, 2007 20:44
Location: Australia

Re: Squares

Post by Richard »

There is a wild duplicate for each missing number.

Code: Select all

'====================================================
' put your choice of numbers in this array
Dim As Short non_binary( 0 To 7 ) = { 1, 2, 4, 9, 17, 34, 68, 136 }

'====================================================
Dim As Short k, sum, n = 0
For k As Short = 0 To 7
    n += non_binary( k )
Next k
Dim As Short freq( 0 To n )

'====================================================
' evaluate binary pattern for all 256 different bytes
For k = 0 To 255
    sum = 0
    If k And 1 Then sum += non_binary( 0 )
    If k And 2 Then sum += non_binary( 1 )
    If k And 4 Then sum += non_binary( 2 )
    If k And 8 Then sum += non_binary( 3 )
    If k And 16 Then sum += non_binary( 4 )
    If k And 32 Then sum += non_binary( 5 )
    If k And 64 Then sum += non_binary( 6 )
    If k And 128 Then sum += non_binary( 7 )
    freq( sum ) += 1    ' accumulate frequency distribution
Next k

'====================================================
' report if missing or duplicate
For k = 0 To n
    If freq( k ) = 0 Then Print k; " is missing."
    If freq( k ) > 1 Then Print k; " is duplicated *"; freq( k )
Next k

Print " Maximum code is"; n
Print " Done. "

'====================================================
Sleep
'====================================================
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

@Richard

Thanks , your a god!!

I'm having all kinds of fun playing with values..
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

It's no fair , altered binary only compresses , if the chr() rolls over 255 , by 10 or more...

Back to the drawing board....
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: Squares

Post by albert »

Another set of altered binary..

1 , 2 , 3 , 6 , 12 , 24 , 48 , 64 : adds up to 160..

So :
If it's 3 = 2 , 1 you can make it 161
if its 6 = 3 , 2 , 1 you can make it 162
If its 12 = 6 , 3 , 2 , 1 you can make it 163 etc.... Up to 255...

???? Got to figure it out...
Locked