Page 1 of 2
Binary Coding To Gray Coding and viceversa
Posted: Mon Feb 18, 2008 9:38 pm
by Psychophanta
Another almost useless code. But who knows, may be you will need it someday
Code: Select all
;Albert (Psychophanta) February 2008:
Procedure.l BinaryCodingToGrayCoding(n.l)
ProcedureReturn n!(n>>1)
EndProcedure
Procedure.l GrayCodingToBinaryCoding(n.l)
Protected t.l=Int(Log(n)/Log(2))
Repeat
n!(Int(Pow(2,t))&n>>1):t-1
Until t<0
ProcedureReturn n
EndProcedure
;Test it:
For t.l=1 To 1000
a.l=Random(3000000)
If a<>BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
Debug "wrong!"
EndIf
Next
Improvements on GrayCodingToBinaryCoding() would be welcome
EDIT 20070219:
In assembler only for longs, not quads supported:
Code: Select all
;Albert (Psychophanta) February 2008:
Procedure.l BinaryCodingToGrayCodingASM(n.l)
!mov eax,dword[p.v_n]
!mov ebx,eax
!shr ebx,1
!xor eax,ebx
ProcedureReturn
EndProcedure
Procedure.l GrayCodingToBinaryCodingASM(n.l)
!mov cl,1
!mov eax,dword[p.v_n]
!@@:mov ebx,eax
!shr ebx,cl
!xor eax,ebx
!shl cl,1
!cmp ebx,2
!jc @f
!cmp cl,32; <- 64 if quads (.q) instead of longs (.l)
!jnz @r
!@@:
ProcedureReturn
EndProcedure
;Test it:
For t.l=1 To 10000
a.l=Random(3000000)
b.l=BinaryCodingToGrayCodingASM(GrayCodingToBinaryCodingASM(a))
If a<>b
Debug "wrong!"
EndIf
Next
Thanks to Demivec and Pupil for their contributions.
Ah! btw, if anyone (for any strange reason) wants a quad ASM standard i386 version (much faster & better than the one from Demivec because this one allows values from 0 to 2^64-1), ask for it
Posted: Mon Feb 18, 2008 10:34 pm
by srod
Interesting one.
When I sat down and constructed the inverse operation, I basically came up with an equivalent method to your GrayCodingToBinaryCoding() algorithm. Absolutely identical.
I'm interested to see if there is a quicker way.
Posted: Tue Feb 19, 2008 3:04 am
by Rook Zimbabwe
So what does it do? What is it used for?
Posted: Tue Feb 19, 2008 9:55 am
by dell_jockey
Rook Zimbabwe wrote:So what does it do? What is it used for?
Nowadays graycodes are predominantly used in signal processing. One such application that I know of is encoding altitude information onto a signal that aircraft transponders return to interrogating radar stations. For more information on this application, see:
http://www.airsport-corp.com/modec.htm
Re: Binary Coding To Gray Coding and viceversa
Posted: Tue Feb 19, 2008 10:43 am
by Demivec
Psychophanta wrote:Improvements on GrayCodingToBinaryCoding() would be welcome
Use this for GrayCodingToBinaryCoding(), it's a gazillion times faster
:
Code: Select all
;Albert (Psychophanta) February 2008:
;with GrayCodingToBinaryCoding() by Demivec
Procedure.q BinaryCodingToGrayCoding(n.q) ;largest integer that is handled is 9223372035781775807
ProcedureReturn n ! (n >> 1)
EndProcedure
Procedure.q GrayCodingToBinaryCoding(n.q) ;largest integer that is handled is 9223372035781775807
Protected s.q = 1,d.q
Repeat
d = n >> s
n ! d
If d < 2 Or s = 4611686018427387904
ProcedureReturn n
EndIf
s << 1
ForEver
EndProcedure
;Test it:
For T.l = 1 To 1000
a.q = 9223372035780000000 + Random(1775807)
b.q = BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
If a <> b
Debug "wrong!"
Break
EndIf
Next
I also updated the code for quad sized conversions. If you only need longs, the Coding functions will work fine as they are for that also (in other words use GrayCodingToBinaryCoding(c.l) and everything is kosher too).
Posted: Tue Feb 19, 2008 3:38 pm
by Psychophanta
Nice Demivec, your method does not make use of arithmetical functions like Log(), etc., but only logical ones, so then your way is more elegant in my opinion, but i don't know if it wins in speed too.
@Rook, you can also look at wikipedia:
http://en.wikipedia.org/wiki/Gray_code
Posted: Tue Feb 19, 2008 4:17 pm
by Rook Zimbabwe
So that is what it was doing. I know we utilized GC in the Army, but I had no real idea about the math!
Oh well... that was for the
@55h0leZ (Officers) to deal with!
Posted: Tue Feb 19, 2008 4:33 pm
by Psychophanta
Damn!
I am stopped!
Why the hell this doesn't work? (it is a question for Coding questions section perhaps).
Code: Select all
Procedure.l BinaryCodingToGrayCoding(n.l)
ProcedureReturn n ! (n >> 1)
EndProcedure
Procedure.l GrayCodingToBinaryCoding(n.l)
Protected s.l = 1,d.l
Repeat
d = n >> s
n ! d
s << 1
Until d<2 Or s=$80000000
ProcedureReturn n
EndProcedure
;Test it:
a.l=500000;Random(1775807)
b.l=BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
If a<>b
Debug "wrong!"
EndIf
Posted: Tue Feb 19, 2008 6:01 pm
by Pupil
Psychophanta wrote:Damn!
I am stopped!
Why the hell this doesn't work? (it is a question for Coding questions section perhaps).
My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.
Posted: Tue Feb 19, 2008 6:19 pm
by Psychophanta
Pupil wrote:My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.
Anyway, in the example there is a positive long value, so that should not affect.
I think the Demivec's method is not correct, and it works casually lucky just due, in part, to the current lacks in quads.
Posted: Tue Feb 19, 2008 6:41 pm
by Pupil
Psychophanta wrote:Pupil wrote:My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.
Anyway, in the example there is a positive long value, so that should not affect.
I think the Demivec's code is not correct, and it works casually lucky just due to the current lacks in quads.
The expression:
will result in all kinds of numbers and the sign bit will be set in the first iteration regardless which positive number you start with. Due to this your version will give the wrong result.
Posted: Tue Feb 19, 2008 7:25 pm
by Psychophanta
Pupil wrote:The expression:
Code:
n ! d
will result in all kinds of numbers and the sign bit will be set in the first iteration regardless which positive number you start with.
Please take a closer look because that can never happen, i.e. more significative bit will never be '1' in that example.
Moreover, you can try: if you replace it by
it continues not working, so that not seem to be the reason
If change
by
it works, and the for the same reason the Demivec version works.
Posted: Tue Feb 19, 2008 8:28 pm
by Pupil
Yes, you're quite right, my misstake. If the signbit isn't set from the begining there shouldn't be any problem like i described.
Instead it seems to be some special condition that occurs when s=32. The asm shift instruction masks the shift length to 5 bits so it interprets the case when s=32 to this "d = n >> 0", this is what causes the faulty result. Change the code to this and se if it works as expected?
Code: Select all
Procedure.l GrayCodingToBinaryCoding(n.l)
Protected s.l = 1,d.l
Repeat
d = n >> s ;& ($7fffffff >> (s-1))
n ! d
s << 1
Until d<2 Or s=32
ProcedureReturn n
EndProcedure
Posted: Tue Feb 19, 2008 8:42 pm
by Psychophanta
Pupil wrote:...it interprets the case when s=32 to this "d = n >> 0", this is what causes the faulty result.
Exactly, it is certainly what there is happening. My last code (which is the same as Demivec algorithm) doesn't work because a bug with >> in longs when the right parameter is 32.
I have discovered it with this code watching the local variables:
Code: Select all
Procedure.l BinaryCodingToGrayCoding(n.l)
ProcedureReturn n ! (n >> 1)
EndProcedure
Procedure.l GrayCodingToBinaryCoding(n.l,nn.q)
Protected s.l = 1,d.l ,dd.q
Repeat
d = n >> s :dd = nn >> s
n ! d:nn!dd
s << 1
Until d<2 And dd<2; Or s=$80000000
ProcedureReturn nn
EndProcedure
;Test it:
a.l=500000;Random(1775807)
CallDebugger
b.l=BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a,a))
If a<>b
Debug "wrong!"
EndIf
My apologies to Demivec when i said his code was not correct, but @Demivec, your code is very very advanced... ... Where did you copied from
Posted: Tue Feb 19, 2008 8:58 pm
by Demivec
Psychophanta wrote:Pupil wrote:My best guess is that the issue arises from the fact that PB uses Arithmetic shift instead of logic shift for the '>>' operator.
Anyway, in the example there is a positive long value, so that should not affect.
I think the Demivec's method is not correct, and it works casually lucky just due, in part, to the current lacks in quads.
@Psychophanta: appology accepted.
My code was been tested with integer values from 0 to 9223372035781775807 before I first posted.
The lack in quads only affects the code I posted because it affects the IF-Endif comparison. That comparison doesn't allow a function that returns a quad to be used in a comparison. I work around this by assigning the function's return value to a variable, then use the variable in the comparison. Quads also can't be returned from Random().
If you want to limit the use of quads you have 2 choices. One, you can just use a long for the input to the function and store the return in a long (this will limit the range of integers to 0 - 2147483646). Two if you change the functions to use only long variables, parameters and returns (this will limit the range of integers to 0 - 131071). If you take the second choice it will dumb the procedure down to the version you are currently trying to debug (hint: it only accepts #'s upto 131071). I went through all these options before I posted the code above. Take your pick.
Your original code could not be used on values equal to zero. It caused a wrap to occur and you had to wait for the value to count down from 2147483647 to 0 before it exited. Try it and see, I used this statement for the time test: GrayCodingToBinaryCoding(0). That's how I came to the precise speed increase of a gazillion times.
One more comment, the "Until d<2 or s=something" is used to determine when shifting any more would be useless. Either it has run out of bits to shift (d<2 which affects shifts to the right) or it has run into a maximum value (s=something, which affects shifts to the left). The shift to the left value is equal to the size of the variable with all bits on except the sign bit (or high bit). For example in my code it equals $4000000000000000.