Re: Need XOR solution
Re: Need XOR solution
- Subject: Re: Need XOR solution
- From: email@hidden (Michael Sullivan)
- Date: Fri, 9 Aug 2002 13:36:57 -0400
- Organization: Society for the Incurably Pompous
>
email@hidden (Michael Sullivan) wrote on Thu, 8 Aug 2002 12:06:43
>
-0400:
>
>Heh. As someone who's done some assembly a very long time ago, it's
>
>absolutely galling that this requires 25 AS numeric instructions (17
>
>with the optimization Nigel mentions later) and a loop construct to do
>
>something that works out to only 1/4 of a processor instruction. (1 XOR
>
>and 3 overhead instructions to get the info in and out of the registers
>
>-- since a G4 has 128 bit words you could be doing 16 bytes at a time
>
>that way, so a single 8-bit byte takes only 1/4 of a processor
>
>instruction).
>
[Sigh...] ;-)
>
>But given AS limitations (no bitwise operations), it's definitely the
>
>way an assembly programmer would solve the problem. I would've used
>
>pretty much the same algorithm, but N.G. beat me to it.
>
Interestingly, this variation - with a couple of extra maths operations
>
per loop - is slightly faster still on both my machines. I'm not sure
>
why. Maybe it's because the maths is contained in just two lines of
>
AppleScript:
>
on xorify(n1, n2)
>
repeat 8 times
>
set n2 to (n2 + (n1 + n2) mod 2 * 256) div 2
>
set n1 to n1 div 2
>
end repeat
>
return n2
>
end xorify
>
(Adding two odd numbers or two even numbers produces an even number,
>
whereas adding an odd and an even produces an odd. This is analogous to
>
XOR and the effect on the lowest-order bit is exactly the same.)
Right, Add and XOR are the same if you ignore carry.
I'm not sure why this is faster. My guess is that AS can do some
optimizations, but only within one line (since it's interpreted, it
can't look at any other lines), so if you can get a bunch of arithmetic
on one line, AS may essentially compile that line of code, and eliminate
any interpreter overhead that you get if you split it onto different
lines. I think we (or Arthur?) noticed that in our prime routines as
well (which may be why you thought of it here, though I didn't).
AS has actually got surprisingly fast raw numerics for an interpreted
language. If vanilla AS allowed bitwise manipulation (char <--> number
conversions, and bitwise AND OR NOT XOR), you could probably do a lot of
stuff that currently sends people to C or other languages.
Michael, or they could always write a compiler...
--
Michael Sullivan
Business Card Express of CT Thermographers to the Trade
Cheshire, CT email@hidden
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.