1*afc2ba1dSToomas Soome /*
2*afc2ba1dSToomas Soome * m a t h 6 4 . c
3*afc2ba1dSToomas Soome * Forth Inspired Command Language - 64 bit math support routines
4*afc2ba1dSToomas Soome * Authors: Michael A. Gauland (gaulandm@mdhost.cse.tek.com)
5*afc2ba1dSToomas Soome * Larry Hastings (larry@hastings.org)
6*afc2ba1dSToomas Soome * John Sadler (john_sadler@alum.mit.edu)
7*afc2ba1dSToomas Soome * Created: 25 January 1998
8*afc2ba1dSToomas Soome * Rev 2.03: Support for 128 bit DP math. This file really ouught to
9*afc2ba1dSToomas Soome * be renamed!
10*afc2ba1dSToomas Soome * $Id: double.c,v 1.2 2010/09/12 15:18:07 asau Exp $
11*afc2ba1dSToomas Soome */
12*afc2ba1dSToomas Soome /*
13*afc2ba1dSToomas Soome * Copyright (c) 1997-2001 John Sadler (john_sadler@alum.mit.edu)
14*afc2ba1dSToomas Soome * All rights reserved.
15*afc2ba1dSToomas Soome *
16*afc2ba1dSToomas Soome * Get the latest Ficl release at http://ficl.sourceforge.net
17*afc2ba1dSToomas Soome *
18*afc2ba1dSToomas Soome * I am interested in hearing from anyone who uses Ficl. If you have
19*afc2ba1dSToomas Soome * a problem, a success story, a defect, an enhancement request, or
20*afc2ba1dSToomas Soome * if you would like to contribute to the Ficl release, please
21*afc2ba1dSToomas Soome * contact me by email at the address above.
22*afc2ba1dSToomas Soome *
23*afc2ba1dSToomas Soome * L I C E N S E and D I S C L A I M E R
24*afc2ba1dSToomas Soome *
25*afc2ba1dSToomas Soome * Redistribution and use in source and binary forms, with or without
26*afc2ba1dSToomas Soome * modification, are permitted provided that the following conditions
27*afc2ba1dSToomas Soome * are met:
28*afc2ba1dSToomas Soome * 1. Redistributions of source code must retain the above copyright
29*afc2ba1dSToomas Soome * notice, this list of conditions and the following disclaimer.
30*afc2ba1dSToomas Soome * 2. Redistributions in binary form must reproduce the above copyright
31*afc2ba1dSToomas Soome * notice, this list of conditions and the following disclaimer in the
32*afc2ba1dSToomas Soome * documentation and/or other materials provided with the distribution.
33*afc2ba1dSToomas Soome *
34*afc2ba1dSToomas Soome * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
35*afc2ba1dSToomas Soome * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36*afc2ba1dSToomas Soome * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37*afc2ba1dSToomas Soome * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
38*afc2ba1dSToomas Soome * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39*afc2ba1dSToomas Soome * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40*afc2ba1dSToomas Soome * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41*afc2ba1dSToomas Soome * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42*afc2ba1dSToomas Soome * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43*afc2ba1dSToomas Soome * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44*afc2ba1dSToomas Soome * SUCH DAMAGE.
45*afc2ba1dSToomas Soome */
46*afc2ba1dSToomas Soome
47*afc2ba1dSToomas Soome #include "ficl.h"
48*afc2ba1dSToomas Soome
49*afc2ba1dSToomas Soome #if FICL_PLATFORM_HAS_2INTEGER
50*afc2ba1dSToomas Soome ficl2UnsignedQR
ficl2UnsignedDivide(ficl2Unsigned q,ficlUnsigned y)51*afc2ba1dSToomas Soome ficl2UnsignedDivide(ficl2Unsigned q, ficlUnsigned y)
52*afc2ba1dSToomas Soome {
53*afc2ba1dSToomas Soome ficl2UnsignedQR result;
54*afc2ba1dSToomas Soome
55*afc2ba1dSToomas Soome result.quotient = q / y;
56*afc2ba1dSToomas Soome /*
57*afc2ba1dSToomas Soome * Once we have the quotient, it's cheaper to calculate the
58*afc2ba1dSToomas Soome * remainder this way than with % (mod). --lch
59*afc2ba1dSToomas Soome */
60*afc2ba1dSToomas Soome result.remainder = (ficlInteger)(q - (result.quotient * y));
61*afc2ba1dSToomas Soome
62*afc2ba1dSToomas Soome return (result);
63*afc2ba1dSToomas Soome }
64*afc2ba1dSToomas Soome
65*afc2ba1dSToomas Soome #else /* FICL_PLATFORM_HAS_2INTEGER */
66*afc2ba1dSToomas Soome
67*afc2ba1dSToomas Soome #define FICL_CELL_HIGH_BIT ((uintmax_t)1 << (FICL_BITS_PER_CELL-1))
68*afc2ba1dSToomas Soome #define UMOD_SHIFT (FICL_BITS_PER_CELL / 2)
69*afc2ba1dSToomas Soome #define UMOD_MASK ((1L << (FICL_BITS_PER_CELL / 2)) - 1)
70*afc2ba1dSToomas Soome
71*afc2ba1dSToomas Soome /*
72*afc2ba1dSToomas Soome * ficl2IntegerIsNegative
73*afc2ba1dSToomas Soome * Returns TRUE if the specified ficl2Unsigned has its sign bit set.
74*afc2ba1dSToomas Soome */
75*afc2ba1dSToomas Soome int
ficl2IntegerIsNegative(ficl2Integer x)76*afc2ba1dSToomas Soome ficl2IntegerIsNegative(ficl2Integer x)
77*afc2ba1dSToomas Soome {
78*afc2ba1dSToomas Soome return (x.high < 0);
79*afc2ba1dSToomas Soome }
80*afc2ba1dSToomas Soome
81*afc2ba1dSToomas Soome /*
82*afc2ba1dSToomas Soome * ficl2IntegerNegate
83*afc2ba1dSToomas Soome * Negates an ficl2Unsigned by complementing and incrementing.
84*afc2ba1dSToomas Soome */
85*afc2ba1dSToomas Soome ficl2Integer
ficl2IntegerNegate(ficl2Integer x)86*afc2ba1dSToomas Soome ficl2IntegerNegate(ficl2Integer x)
87*afc2ba1dSToomas Soome {
88*afc2ba1dSToomas Soome x.high = ~x.high;
89*afc2ba1dSToomas Soome x.low = ~x.low;
90*afc2ba1dSToomas Soome x.low ++;
91*afc2ba1dSToomas Soome if (x.low == 0)
92*afc2ba1dSToomas Soome x.high++;
93*afc2ba1dSToomas Soome
94*afc2ba1dSToomas Soome return (x);
95*afc2ba1dSToomas Soome }
96*afc2ba1dSToomas Soome
97*afc2ba1dSToomas Soome /*
98*afc2ba1dSToomas Soome * ficl2UnsignedMultiplyAccumulate
99*afc2ba1dSToomas Soome * Mixed precision multiply and accumulate primitive for number building.
100*afc2ba1dSToomas Soome * Multiplies ficl2Unsigned u by ficlUnsigned mul and adds ficlUnsigned add.
101*afc2ba1dSToomas Soome * Mul is typically the numeric base, and add represents a digit to be
102*afc2ba1dSToomas Soome * appended to the growing number.
103*afc2ba1dSToomas Soome * Returns the result of the operation
104*afc2ba1dSToomas Soome */
105*afc2ba1dSToomas Soome ficl2Unsigned
ficl2UnsignedMultiplyAccumulate(ficl2Unsigned u,ficlUnsigned mul,ficlUnsigned add)106*afc2ba1dSToomas Soome ficl2UnsignedMultiplyAccumulate(ficl2Unsigned u, ficlUnsigned mul,
107*afc2ba1dSToomas Soome ficlUnsigned add)
108*afc2ba1dSToomas Soome {
109*afc2ba1dSToomas Soome ficl2Unsigned resultLo = ficl2UnsignedMultiply(u.low, mul);
110*afc2ba1dSToomas Soome ficl2Unsigned resultHi = ficl2UnsignedMultiply(u.high, mul);
111*afc2ba1dSToomas Soome resultLo.high += resultHi.low;
112*afc2ba1dSToomas Soome resultHi.low = resultLo.low + add;
113*afc2ba1dSToomas Soome
114*afc2ba1dSToomas Soome if (resultHi.low < resultLo.low)
115*afc2ba1dSToomas Soome resultLo.high++;
116*afc2ba1dSToomas Soome
117*afc2ba1dSToomas Soome resultLo.low = resultHi.low;
118*afc2ba1dSToomas Soome
119*afc2ba1dSToomas Soome return (resultLo);
120*afc2ba1dSToomas Soome }
121*afc2ba1dSToomas Soome
122*afc2ba1dSToomas Soome /*
123*afc2ba1dSToomas Soome * ficl2IntegerMultiply
124*afc2ba1dSToomas Soome * Multiplies a pair of ficlIntegers and returns an ficl2Integer result.
125*afc2ba1dSToomas Soome */
126*afc2ba1dSToomas Soome ficl2Integer
ficl2IntegerMultiply(ficlInteger x,ficlInteger y)127*afc2ba1dSToomas Soome ficl2IntegerMultiply(ficlInteger x, ficlInteger y)
128*afc2ba1dSToomas Soome {
129*afc2ba1dSToomas Soome ficl2Unsigned prod;
130*afc2ba1dSToomas Soome ficl2Integer result;
131*afc2ba1dSToomas Soome int sign = 1;
132*afc2ba1dSToomas Soome
133*afc2ba1dSToomas Soome if (x < 0) {
134*afc2ba1dSToomas Soome sign = -sign;
135*afc2ba1dSToomas Soome x = -x;
136*afc2ba1dSToomas Soome }
137*afc2ba1dSToomas Soome
138*afc2ba1dSToomas Soome if (y < 0) {
139*afc2ba1dSToomas Soome sign = -sign;
140*afc2ba1dSToomas Soome y = -y;
141*afc2ba1dSToomas Soome }
142*afc2ba1dSToomas Soome
143*afc2ba1dSToomas Soome prod = ficl2UnsignedMultiply(x, y);
144*afc2ba1dSToomas Soome FICL_2INTEGER_SET(FICL_2UNSIGNED_GET_HIGH(prod),
145*afc2ba1dSToomas Soome FICL_2UNSIGNED_GET_LOW(prod), result);
146*afc2ba1dSToomas Soome if (sign > 0)
147*afc2ba1dSToomas Soome return (result);
148*afc2ba1dSToomas Soome else
149*afc2ba1dSToomas Soome return (ficl2IntegerNegate(result));
150*afc2ba1dSToomas Soome }
151*afc2ba1dSToomas Soome
152*afc2ba1dSToomas Soome ficl2Integer
ficl2IntegerDecrement(ficl2Integer x)153*afc2ba1dSToomas Soome ficl2IntegerDecrement(ficl2Integer x)
154*afc2ba1dSToomas Soome {
155*afc2ba1dSToomas Soome if (x.low == INTMAX_MIN)
156*afc2ba1dSToomas Soome x.high--;
157*afc2ba1dSToomas Soome x.low--;
158*afc2ba1dSToomas Soome
159*afc2ba1dSToomas Soome return (x);
160*afc2ba1dSToomas Soome }
161*afc2ba1dSToomas Soome
162*afc2ba1dSToomas Soome ficl2Unsigned
ficl2UnsignedAdd(ficl2Unsigned x,ficl2Unsigned y)163*afc2ba1dSToomas Soome ficl2UnsignedAdd(ficl2Unsigned x, ficl2Unsigned y)
164*afc2ba1dSToomas Soome {
165*afc2ba1dSToomas Soome ficl2Unsigned result;
166*afc2ba1dSToomas Soome
167*afc2ba1dSToomas Soome result.high = x.high + y.high;
168*afc2ba1dSToomas Soome result.low = x.low + y.low;
169*afc2ba1dSToomas Soome
170*afc2ba1dSToomas Soome if (result.low < y.low)
171*afc2ba1dSToomas Soome result.high++;
172*afc2ba1dSToomas Soome
173*afc2ba1dSToomas Soome return (result);
174*afc2ba1dSToomas Soome }
175*afc2ba1dSToomas Soome
176*afc2ba1dSToomas Soome /*
177*afc2ba1dSToomas Soome * ficl2UnsignedMultiply
178*afc2ba1dSToomas Soome * Contributed by:
179*afc2ba1dSToomas Soome * Michael A. Gauland gaulandm@mdhost.cse.tek.com
180*afc2ba1dSToomas Soome */
181*afc2ba1dSToomas Soome ficl2Unsigned
ficl2UnsignedMultiply(ficlUnsigned x,ficlUnsigned y)182*afc2ba1dSToomas Soome ficl2UnsignedMultiply(ficlUnsigned x, ficlUnsigned y)
183*afc2ba1dSToomas Soome {
184*afc2ba1dSToomas Soome ficl2Unsigned result = { 0, 0 };
185*afc2ba1dSToomas Soome ficl2Unsigned addend;
186*afc2ba1dSToomas Soome
187*afc2ba1dSToomas Soome addend.low = y;
188*afc2ba1dSToomas Soome addend.high = 0; /* No sign extension--arguments are unsigned */
189*afc2ba1dSToomas Soome
190*afc2ba1dSToomas Soome while (x != 0) {
191*afc2ba1dSToomas Soome if (x & 1) {
192*afc2ba1dSToomas Soome result = ficl2UnsignedAdd(result, addend);
193*afc2ba1dSToomas Soome }
194*afc2ba1dSToomas Soome x >>= 1;
195*afc2ba1dSToomas Soome addend = ficl2UnsignedArithmeticShiftLeft(addend);
196*afc2ba1dSToomas Soome }
197*afc2ba1dSToomas Soome return (result);
198*afc2ba1dSToomas Soome }
199*afc2ba1dSToomas Soome
200*afc2ba1dSToomas Soome /*
201*afc2ba1dSToomas Soome * ficl2UnsignedSubtract
202*afc2ba1dSToomas Soome */
203*afc2ba1dSToomas Soome ficl2Unsigned
ficl2UnsignedSubtract(ficl2Unsigned x,ficl2Unsigned y)204*afc2ba1dSToomas Soome ficl2UnsignedSubtract(ficl2Unsigned x, ficl2Unsigned y)
205*afc2ba1dSToomas Soome {
206*afc2ba1dSToomas Soome ficl2Unsigned result;
207*afc2ba1dSToomas Soome
208*afc2ba1dSToomas Soome result.high = x.high - y.high;
209*afc2ba1dSToomas Soome result.low = x.low - y.low;
210*afc2ba1dSToomas Soome
211*afc2ba1dSToomas Soome if (x.low < y.low) {
212*afc2ba1dSToomas Soome result.high--;
213*afc2ba1dSToomas Soome }
214*afc2ba1dSToomas Soome
215*afc2ba1dSToomas Soome return (result);
216*afc2ba1dSToomas Soome }
217*afc2ba1dSToomas Soome
218*afc2ba1dSToomas Soome /*
219*afc2ba1dSToomas Soome * ficl2UnsignedArithmeticShiftLeft
220*afc2ba1dSToomas Soome * 64 bit left shift
221*afc2ba1dSToomas Soome */
222*afc2ba1dSToomas Soome ficl2Unsigned
ficl2UnsignedArithmeticShiftLeft(ficl2Unsigned x)223*afc2ba1dSToomas Soome ficl2UnsignedArithmeticShiftLeft(ficl2Unsigned x)
224*afc2ba1dSToomas Soome {
225*afc2ba1dSToomas Soome ficl2Unsigned result;
226*afc2ba1dSToomas Soome
227*afc2ba1dSToomas Soome result.high = x.high << 1;
228*afc2ba1dSToomas Soome if (x.low & FICL_CELL_HIGH_BIT) {
229*afc2ba1dSToomas Soome result.high++;
230*afc2ba1dSToomas Soome }
231*afc2ba1dSToomas Soome
232*afc2ba1dSToomas Soome result.low = x.low << 1;
233*afc2ba1dSToomas Soome
234*afc2ba1dSToomas Soome return (result);
235*afc2ba1dSToomas Soome }
236*afc2ba1dSToomas Soome
237*afc2ba1dSToomas Soome /*
238*afc2ba1dSToomas Soome * ficl2UnsignedArithmeticShiftRight
239*afc2ba1dSToomas Soome * 64 bit right shift (unsigned - no sign extend)
240*afc2ba1dSToomas Soome */
241*afc2ba1dSToomas Soome ficl2Unsigned
ficl2UnsignedArithmeticShiftRight(ficl2Unsigned x)242*afc2ba1dSToomas Soome ficl2UnsignedArithmeticShiftRight(ficl2Unsigned x)
243*afc2ba1dSToomas Soome {
244*afc2ba1dSToomas Soome ficl2Unsigned result;
245*afc2ba1dSToomas Soome
246*afc2ba1dSToomas Soome result.low = x.low >> 1;
247*afc2ba1dSToomas Soome if (x.high & 1) {
248*afc2ba1dSToomas Soome result.low |= FICL_CELL_HIGH_BIT;
249*afc2ba1dSToomas Soome }
250*afc2ba1dSToomas Soome
251*afc2ba1dSToomas Soome result.high = x.high >> 1;
252*afc2ba1dSToomas Soome return (result);
253*afc2ba1dSToomas Soome }
254*afc2ba1dSToomas Soome
255*afc2ba1dSToomas Soome /*
256*afc2ba1dSToomas Soome * ficl2UnsignedOr
257*afc2ba1dSToomas Soome * 64 bit bitwise OR
258*afc2ba1dSToomas Soome */
259*afc2ba1dSToomas Soome ficl2Unsigned
ficl2UnsignedOr(ficl2Unsigned x,ficl2Unsigned y)260*afc2ba1dSToomas Soome ficl2UnsignedOr(ficl2Unsigned x, ficl2Unsigned y)
261*afc2ba1dSToomas Soome {
262*afc2ba1dSToomas Soome ficl2Unsigned result;
263*afc2ba1dSToomas Soome
264*afc2ba1dSToomas Soome result.high = x.high | y.high;
265*afc2ba1dSToomas Soome result.low = x.low | y.low;
266*afc2ba1dSToomas Soome
267*afc2ba1dSToomas Soome return (result);
268*afc2ba1dSToomas Soome }
269*afc2ba1dSToomas Soome
270*afc2ba1dSToomas Soome /*
271*afc2ba1dSToomas Soome * ficl2UnsignedCompare
272*afc2ba1dSToomas Soome * Return -1 if x < y; 0 if x==y, and 1 if x > y.
273*afc2ba1dSToomas Soome */
274*afc2ba1dSToomas Soome int
ficl2UnsignedCompare(ficl2Unsigned x,ficl2Unsigned y)275*afc2ba1dSToomas Soome ficl2UnsignedCompare(ficl2Unsigned x, ficl2Unsigned y)
276*afc2ba1dSToomas Soome {
277*afc2ba1dSToomas Soome if (x.high > y.high)
278*afc2ba1dSToomas Soome return (1);
279*afc2ba1dSToomas Soome if (x.high < y.high)
280*afc2ba1dSToomas Soome return (-1);
281*afc2ba1dSToomas Soome
282*afc2ba1dSToomas Soome /* High parts are equal */
283*afc2ba1dSToomas Soome
284*afc2ba1dSToomas Soome if (x.low > y.low)
285*afc2ba1dSToomas Soome return (1);
286*afc2ba1dSToomas Soome else if (x.low < y.low)
287*afc2ba1dSToomas Soome return (-1);
288*afc2ba1dSToomas Soome
289*afc2ba1dSToomas Soome return (0);
290*afc2ba1dSToomas Soome }
291*afc2ba1dSToomas Soome
292*afc2ba1dSToomas Soome /*
293*afc2ba1dSToomas Soome * ficl2UnsignedDivide
294*afc2ba1dSToomas Soome * Portable versions of ficl2Multiply and ficl2Divide in C
295*afc2ba1dSToomas Soome * Contributed by:
296*afc2ba1dSToomas Soome * Michael A. Gauland gaulandm@mdhost.cse.tek.com
297*afc2ba1dSToomas Soome */
298*afc2ba1dSToomas Soome ficl2UnsignedQR
ficl2UnsignedDivide(ficl2Unsigned q,ficlUnsigned y)299*afc2ba1dSToomas Soome ficl2UnsignedDivide(ficl2Unsigned q, ficlUnsigned y)
300*afc2ba1dSToomas Soome {
301*afc2ba1dSToomas Soome ficl2UnsignedQR result;
302*afc2ba1dSToomas Soome ficl2Unsigned quotient;
303*afc2ba1dSToomas Soome ficl2Unsigned subtrahend;
304*afc2ba1dSToomas Soome ficl2Unsigned mask;
305*afc2ba1dSToomas Soome
306*afc2ba1dSToomas Soome quotient.low = 0;
307*afc2ba1dSToomas Soome quotient.high = 0;
308*afc2ba1dSToomas Soome
309*afc2ba1dSToomas Soome subtrahend.low = y;
310*afc2ba1dSToomas Soome subtrahend.high = 0;
311*afc2ba1dSToomas Soome
312*afc2ba1dSToomas Soome mask.low = 1;
313*afc2ba1dSToomas Soome mask.high = 0;
314*afc2ba1dSToomas Soome
315*afc2ba1dSToomas Soome while ((ficl2UnsignedCompare(subtrahend, q) < 0) &&
316*afc2ba1dSToomas Soome (subtrahend.high & FICL_CELL_HIGH_BIT) == 0) {
317*afc2ba1dSToomas Soome mask = ficl2UnsignedArithmeticShiftLeft(mask);
318*afc2ba1dSToomas Soome subtrahend = ficl2UnsignedArithmeticShiftLeft(subtrahend);
319*afc2ba1dSToomas Soome }
320*afc2ba1dSToomas Soome
321*afc2ba1dSToomas Soome while (mask.low != 0 || mask.high != 0) {
322*afc2ba1dSToomas Soome if (ficl2UnsignedCompare(subtrahend, q) <= 0) {
323*afc2ba1dSToomas Soome q = ficl2UnsignedSubtract(q, subtrahend);
324*afc2ba1dSToomas Soome quotient = ficl2UnsignedOr(quotient, mask);
325*afc2ba1dSToomas Soome }
326*afc2ba1dSToomas Soome mask = ficl2UnsignedArithmeticShiftRight(mask);
327*afc2ba1dSToomas Soome subtrahend = ficl2UnsignedArithmeticShiftRight(subtrahend);
328*afc2ba1dSToomas Soome }
329*afc2ba1dSToomas Soome
330*afc2ba1dSToomas Soome result.quotient = quotient;
331*afc2ba1dSToomas Soome result.remainder = q.low;
332*afc2ba1dSToomas Soome return (result);
333*afc2ba1dSToomas Soome }
334*afc2ba1dSToomas Soome #endif /* !FICL_PLATFORM_HAS_2INTEGER */
335*afc2ba1dSToomas Soome
336*afc2ba1dSToomas Soome /*
337*afc2ba1dSToomas Soome * ficl2IntegerDivideFloored
338*afc2ba1dSToomas Soome *
339*afc2ba1dSToomas Soome * FROM THE FORTH ANS...
340*afc2ba1dSToomas Soome * Floored division is integer division in which the remainder carries
341*afc2ba1dSToomas Soome * the sign of the divisor or is zero, and the quotient is rounded to
342*afc2ba1dSToomas Soome * its arithmetic floor. Symmetric division is integer division in which
343*afc2ba1dSToomas Soome * the remainder carries the sign of the dividend or is zero and the
344*afc2ba1dSToomas Soome * quotient is the mathematical quotient rounded towards zero or
345*afc2ba1dSToomas Soome * truncated. Examples of each are shown in tables 3.3 and 3.4.
346*afc2ba1dSToomas Soome *
347*afc2ba1dSToomas Soome * Table 3.3 - Floored Division Example
348*afc2ba1dSToomas Soome * Dividend Divisor Remainder Quotient
349*afc2ba1dSToomas Soome * -------- ------- --------- --------
350*afc2ba1dSToomas Soome * 10 7 3 1
351*afc2ba1dSToomas Soome * -10 7 4 -2
352*afc2ba1dSToomas Soome * 10 -7 -4 -2
353*afc2ba1dSToomas Soome * -10 -7 -3 1
354*afc2ba1dSToomas Soome *
355*afc2ba1dSToomas Soome *
356*afc2ba1dSToomas Soome * Table 3.4 - Symmetric Division Example
357*afc2ba1dSToomas Soome * Dividend Divisor Remainder Quotient
358*afc2ba1dSToomas Soome * -------- ------- --------- --------
359*afc2ba1dSToomas Soome * 10 7 3 1
360*afc2ba1dSToomas Soome * -10 7 -3 -1
361*afc2ba1dSToomas Soome * 10 -7 3 -1
362*afc2ba1dSToomas Soome * -10 -7 -3 1
363*afc2ba1dSToomas Soome */
364*afc2ba1dSToomas Soome ficl2IntegerQR
ficl2IntegerDivideFloored(ficl2Integer num,ficlInteger den)365*afc2ba1dSToomas Soome ficl2IntegerDivideFloored(ficl2Integer num, ficlInteger den)
366*afc2ba1dSToomas Soome {
367*afc2ba1dSToomas Soome ficl2IntegerQR qr;
368*afc2ba1dSToomas Soome ficl2UnsignedQR uqr;
369*afc2ba1dSToomas Soome ficl2Unsigned u;
370*afc2ba1dSToomas Soome int signRem = 1;
371*afc2ba1dSToomas Soome int signQuot = 1;
372*afc2ba1dSToomas Soome
373*afc2ba1dSToomas Soome if (ficl2IntegerIsNegative(num)) {
374*afc2ba1dSToomas Soome num = ficl2IntegerNegate(num);
375*afc2ba1dSToomas Soome signQuot = -signQuot;
376*afc2ba1dSToomas Soome }
377*afc2ba1dSToomas Soome
378*afc2ba1dSToomas Soome if (den < 0) {
379*afc2ba1dSToomas Soome den = -den;
380*afc2ba1dSToomas Soome signRem = -signRem;
381*afc2ba1dSToomas Soome signQuot = -signQuot;
382*afc2ba1dSToomas Soome }
383*afc2ba1dSToomas Soome
384*afc2ba1dSToomas Soome FICL_2UNSIGNED_SET(FICL_2UNSIGNED_GET_HIGH(num),
385*afc2ba1dSToomas Soome FICL_2UNSIGNED_GET_LOW(num), u);
386*afc2ba1dSToomas Soome uqr = ficl2UnsignedDivide(u, (ficlUnsigned)den);
387*afc2ba1dSToomas Soome qr = FICL_2UNSIGNEDQR_TO_2INTEGERQR(uqr);
388*afc2ba1dSToomas Soome if (signQuot < 0) {
389*afc2ba1dSToomas Soome qr.quotient = ficl2IntegerNegate(qr.quotient);
390*afc2ba1dSToomas Soome if (qr.remainder != 0) {
391*afc2ba1dSToomas Soome qr.quotient = ficl2IntegerDecrement(qr.quotient);
392*afc2ba1dSToomas Soome qr.remainder = den - qr.remainder;
393*afc2ba1dSToomas Soome }
394*afc2ba1dSToomas Soome }
395*afc2ba1dSToomas Soome
396*afc2ba1dSToomas Soome if (signRem < 0)
397*afc2ba1dSToomas Soome qr.remainder = -qr.remainder;
398*afc2ba1dSToomas Soome
399*afc2ba1dSToomas Soome return (qr);
400*afc2ba1dSToomas Soome }
401*afc2ba1dSToomas Soome
402*afc2ba1dSToomas Soome /*
403*afc2ba1dSToomas Soome * ficl2IntegerDivideSymmetric
404*afc2ba1dSToomas Soome * Divide an ficl2Unsigned by a ficlInteger and return a ficlInteger quotient
405*afc2ba1dSToomas Soome * and a ficlInteger remainder. The absolute values of quotient and remainder
406*afc2ba1dSToomas Soome * are not affected by the signs of the numerator and denominator
407*afc2ba1dSToomas Soome * (the operation is symmetric on the number line)
408*afc2ba1dSToomas Soome */
409*afc2ba1dSToomas Soome ficl2IntegerQR
ficl2IntegerDivideSymmetric(ficl2Integer num,ficlInteger den)410*afc2ba1dSToomas Soome ficl2IntegerDivideSymmetric(ficl2Integer num, ficlInteger den)
411*afc2ba1dSToomas Soome {
412*afc2ba1dSToomas Soome ficl2IntegerQR qr;
413*afc2ba1dSToomas Soome ficl2UnsignedQR uqr;
414*afc2ba1dSToomas Soome ficl2Unsigned u;
415*afc2ba1dSToomas Soome int signRem = 1;
416*afc2ba1dSToomas Soome int signQuot = 1;
417*afc2ba1dSToomas Soome
418*afc2ba1dSToomas Soome if (ficl2IntegerIsNegative(num)) {
419*afc2ba1dSToomas Soome num = ficl2IntegerNegate(num);
420*afc2ba1dSToomas Soome signRem = -signRem;
421*afc2ba1dSToomas Soome signQuot = -signQuot;
422*afc2ba1dSToomas Soome }
423*afc2ba1dSToomas Soome
424*afc2ba1dSToomas Soome if (den < 0) {
425*afc2ba1dSToomas Soome den = -den;
426*afc2ba1dSToomas Soome signQuot = -signQuot;
427*afc2ba1dSToomas Soome }
428*afc2ba1dSToomas Soome
429*afc2ba1dSToomas Soome FICL_2UNSIGNED_SET(FICL_2UNSIGNED_GET_HIGH(num),
430*afc2ba1dSToomas Soome FICL_2UNSIGNED_GET_LOW(num), u);
431*afc2ba1dSToomas Soome uqr = ficl2UnsignedDivide(u, (ficlUnsigned)den);
432*afc2ba1dSToomas Soome qr = FICL_2UNSIGNEDQR_TO_2INTEGERQR(uqr);
433*afc2ba1dSToomas Soome if (signRem < 0)
434*afc2ba1dSToomas Soome qr.remainder = -qr.remainder;
435*afc2ba1dSToomas Soome
436*afc2ba1dSToomas Soome if (signQuot < 0)
437*afc2ba1dSToomas Soome qr.quotient = ficl2IntegerNegate(qr.quotient);
438*afc2ba1dSToomas Soome
439*afc2ba1dSToomas Soome return (qr);
440*afc2ba1dSToomas Soome }
441