Page 2 of 2
Posted: Tue Feb 19, 2008 9:15 pm
by Psychophanta
Demivec wrote: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.
Tested before to post it. And also now.
Please take a closer look because you are very wrong this time.
Demivec wrote: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.
Again wrong.
For your example code $40 is enough. There is a nonsense more than $40 when dealing with quads. And there is a nonsense more than $20 for longs.
Here it is a nice version:
Code: Select all
;Albert (Psychophanta) February 2008:
;with GrayCodingToBinaryCoding() by Demivec
;improved GrayCodingToBinaryCoding() by Pupil
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=32; <- s=64 if quads (.q) are used instead of longs (.l)
ProcedureReturn n
EndProcedure
;Test it:
For t.l=1 To 1000
a.l=Random(3000000)
If a<>BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
Debug "wrong!"
EndIf
Next
Posted: Tue Feb 19, 2008 9:28 pm
by Demivec
Psychophanta wrote:Demivec wrote: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.
Tested before to post it. And also now.
Please take a closer look because you are very wrong this time.
Demivec wrote: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.
Again wrong.
For your example code $40 is enough. There is a nonsense more than $40 when dealing with quads. And there is a nonsense more than $20 for longs.
Here it is a nice version:
Code: Select all
;Albert (Psychophanta) February 2008:
;with GrayCodingToBinaryCoding() by Demivec
;improved GrayCodingToBinaryCoding() by Pupil
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=32; <- s=64 if quads (.q) are used instead of longs (.l)
ProcedureReturn n
EndProcedure
;Test it:
For t.l=1 To 1000
a.l=Random(3000000)
If a<>BinaryCodingToGrayCoding(GrayCodingToBinaryCoding(a))
Debug "wrong!"
EndIf
Next
@Psychophanta: now it's my turn to appologize. To make up for it, I made an improvement and eliminated the check with the variable "s". Your logic made me see the error of my ways, it was a redundant check because I had used the wrong value in it and my version still worked. I also added an error check as well if an illegal value is supplied. Should be faster yet (no, i didn't time it
)
Code: Select all
Procedure.q GrayCodingToBinaryCoding(n.q) ;largest integer that is handled is 9223372035781775807
Protected s.l = 1,d.q
If n<0
ProcedureReturn -1 ;bad parameter value, can't be negative
EndIf
Repeat
d = n >> s
n ! d
If d < 2
ProcedureReturn n
EndIf
s << 1
ForEver
EndProcedure
@Edit: Updated code to change "s.q" to "s.l"
Posted: Tue Feb 19, 2008 11:07 pm
by Psychophanta
Apologies accepted of course.
Made your written algorithm in asm, but for longs only (quads is another history, could be made a nice one using SSE or so):
Code: Select all
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 cl,32
!jnz @r
ProcedureReturn
EndProcedure
EDIT: Final optimized codes at first post.