ritter@versatc.versatec.COM (Jack Ritter) (02/27/90)
I have a problem. I've inplemented the Newell & Sequin
algorithm for breaking up an arbitrary (2d) polygon into
a minimum # of trapezoids. I originally wrote the intersection()
routine in 68020 assembly. I used 68020's "quad word" arithmetic, which
allows multiplying 2 longs to get a 64 bit (quad word) intermediate
result, then dividing down to a 32 bit result (computing the
intersection of 2 arbitrary edges requires this kind of
accumulation because you must make a product of products before
dividing). This code worked very well, because I had complete control
over the arithmetic, I looked for overflow, carry, etc.
The problem is this: I must now implement the same algorithm
in C. C has no ability to do quad word arithmetic. I've tried
breaking up a 32X32 -> 64 muiltiply into factors, but you still
need to detect carry. The alternative is floating point, but even
by being careful about F.P. rounding, I get slightly different
results than the original assembly code.
How can I do double precision fixed-point arithmetic in C?
--
Versatec, Inc.
Jack Ritter, M.S. 1-7
2710 Walsh Ave.
P.O. Box 58091
Santa Clara, CA 95052-8091
(408)982-4332, or (408)988-2800 X 5743
UUCP: {ames,apple,sun,pyramid}!versatc!ritter
--( / __ - .. (( /
/ / -- ) . \ \ // . (
/ ** ) // _*_ // * ..
) (( . \ / . * ) //kassover@control.crd.ge.com (David Kassover) (03/01/90)
In article <20408@versatc.versatec.COM> ritter@versatc.versatec.COM (Jack Ritter) writes: ... > > How can I do double precision fixed-point arithmetic in C? >-- Easy (to say, anyway) you write a bunch of routines (maybe you want them to be functions) that explicitly do the arithmetic you want to do. Then you call the routines instead of combine variables with operators. E.G. for addition, you add the two lower order segments together, checking for overflow. Then you add the two higher order segments, and add 1 if there was overflow from the previous addition. Then you glom both parts back into your data structure. If this were Ada, which it is not (If I were vulgar...*), you could write your functions carefully and overload them onto the operators... I'm not a C guru, so I don't know if integer overflow is detectable in any standard form of the language... Or maybe you could ignore overflow, then examine the two lower order segments carefully to determine if there *should* have been an overflow? It begins to be not hardly worth the effort. Perhaps you can get permission to implement THESE ROUTINES in local assembler and call them from your main program.
kassover@jupiter.crd.ge.com (David Kassover) (03/02/90)
In article <5637@crdgw1.crd.ge.com> kassover@control.crd.ge.com (David Kassover) writes: ... That's me... >It begins to be not hardly worth the effort. Perhaps you can get >permission to implement THESE ROUTINES in local assembler and >call them from your main program. I checked with one of my C/Unix gurus. He assured me that *maybe* you could trap one of the unix standard signals for integer overflow, but you would be advised to write a short experiment to verify it. Further, you have access to the bitwise representation of your int's, and therefore moderately simple to check for overflow. The sizeof function will return the length of an int in bytes. The hard part is knowing how many bits/byte. It seems, from an examination of K&R, that you have to glean that information from the underlying platform documentation, and build it into your procedures. I know of one architecture which has 64 bit words, 8 bit bytes, but uses only 56 bits out of the 64 for integers. (Don't laugh, this way they can use the floating point hardware for integer operations) Let us know how it all comes out. Dave