/****************************************************************************/
/*
*/
/* int MultDiv(unsigned long *FactorsIn, int QFactors,
*/
/*
unsigned long *DivisorsIn, int QDivisors,
*/
/*
unsigned long *Result)
*/
/*
*/
/* Purpose: Perform multiplications
and divisions with long */
/*
variables to keep the most precision, without invoking */
/*
the floating-point libraries.
*/
/*
*/
/*
Please note the important Dependencies.
*/
/*
*/
/* Calls: none
*/
/*
*/
/* Inputs: unsigned
long *Factor -pointer to array of Factors */
/*
int QFactors
-Quantity of Factors. p;
*/
/*
unsigned long *DivisorsIn
*/
/*
-pointer to array of Divisors, **/
/*
int QDivisors
-Quantity of Divisors. 20 max. **/
/*
*/
/* Outputs: unsigned long
*Result -is set to zero when exiting */
/*
with any return code other */
/*
than OK.
*/
/*
*/
/*
int Return Code: CANTDO -Inability to complete the calc */
/*
(will be History-logged) */
/*
TOOHI -Result exceeds MAX_PAR_VALUE */
/*
TOOLOW -Result would be <= 0
*/
/*
OK -Paradise on Earth
*/
/*
*/
/*
*/
/* Dependencies: Divisors larger than 2*65536 = 131,072
should not be */
/*
used. (History Log Data 0)
*/
/*
*/
/*
Factors larger than 0xFFFFFFFF/9999 = 429,539 should */
/*
not be used. (1)
*/
/*
*/
/*
No more than twenty input divisors may be supplied. (2 */
/*
and 3)
*/
/*
*/
/*
*/
/* Err Conditions: A History Log entry of MULTDIVPROCESS_TYPE will
be */
/*
generated if this function returns CANTDO.
*/
/*
*/
/*
*/
/*
History Log Data 0:
*/
/*
*/
/*
Possible overflow of long if factors and divisors that */
/*
are too large are used; the return code will be set to */
/*
CANTDO and the function will exit if neither the
*/
/*
remaining factors nor the remaining divisors will give */
/*
an intermediate result that fits within the "long"
*/
/*
type.
*/
/*
*/
/*
This will happen if only divisors more than twice
*/
/*
as large as the largest possible product that will fit */
/*
in a "long" are used, based on the factors supplied
*/
/*
that were used and remain. The "CANTDO" will result if */
/*
factors still remain at that time, otherwise a simple */
/*
and accurate TOOLOW will result if no factors remain. */
/*
*/
/*
That is, this will happen if Factors whose product
*/
/*
exceeds the maximum value that can fit in an unsigned */
/*
long are used and if Divisors are used that exceed the */
/*
intermediate product of the Factors used at that time */
/*
by more than two. (eg 70,000 and 70,000 with a Divisor */
/*
of 145,000, because 70,000 times 70,000 exceeds the
*/
/*
long variable type and 70,000 divided by 145,000 can't */
/*
be rounded up -- or rather I have decided not to accept */
/*
results that small because I wish to keep the precision */
/*
maintenance carrying intermediate results of at least */
/*
1000). In fact, the smallest factor that might cause */
/*
this problem if used twice would be 65536, the square */
/*
root of 2^32, if a divisor of larger than twice that is */
/*
also used.
*/
/*
*/
/*
In general, Divisors (and Factors too) larger than
*/
/*
five-digit values (what can be typed into the pump
*/
/*
given its display) are not used because this routine */
/*
is intended for use in doing calculations with entered */
/*
parameter values. However, the upper divisor limit is */
/*
2*65536 = 131,072 (one more and the long-overflow
*/
/*
problem might occur - a larger factor and divisor might */
/*
cause this problem, but this is the lowest divisor at */
/*
which a problem might occur), and the upper Factor
*/
/*
limit is as stated next.
*/
/*
Another thing is that, due to precision-fixing, a
*/
/*
divisor times 10,000 cannot exceed the long value,
*/
/*
because a remainder might be almost as large as a
*/
/*
divisor, and it is multiplied by 10,000 for precision- */
/*
fixing. This puts another upper limit for divisors, of */
/*
0xFFFFFFFF/10,000 = 429,496. However, this exceeds the */
/*
upper limit of 131,072, so it will be obeyed if the
*/
/*
latter is obeyed.
*/
/*
*/
/*
(The History log data will be set to 0 and the History */
/*
Log message would be "Intermediate result overflows
*/
/*
long in MultDiv" if it appears in the History Log.
*/
/*
*/
/*
*/
/*
History Log Data 1:
*/
/*
*/
/*
The function will also return CANTDO if Factors larger */
/*
than 0xFFFFFFFF/9999 = 429,539 are used, which might */
/*
cause no more factors to be able to fit if the function */
/*
has finished with all of the supplied divisors. The
*/
/*
infinite loop that would otherwise occur (because the */
/*
precision-fix divisor would have to be used, but then */
/*
would be restored because the intermediate result was */
/*
made less than a four-digit value) will be detected. */
/*
*/
/*
(The History log data will be set to 1 and the History */
/*
Log message would be "Precision and large factor
*/
/*
conflict in MultDiv".)
*/
/*
*/
/*
*/
/*
History Log Data 2 and 3:
*/
/*
*/
/*
If an intermediate quantity of divisors exceeds 20,
*/
/*
which would overflow the Divisor Array, this function */
/*
will return CANTDO. (Extra divisors are generated by */
/*
this function as it works, but they are then erased by */
/*
this function after being used, and this function
*/
/*
creates an internal divisor array of size 20, so this */
/*
would be an unexpected error)
*/
/*
(History log data will be set to 2 and the History Log */
/*
message would be "Working divisors overflowed array in */
/*
MultDiv")
*/
/*
(History log data will be set to 3 if there are more */
/*
than 20 input Divisors, and the History Log message
*/
/*
would be "Too many divisors supplied to MultDiv")
*/
/*
*/
/*
*/
/*
The programmer using this function will have to ensure
*/
/*
that all data will be in range.
*/
/*
*/
/* Notes:
*/
/*
*/
/* This routine uses all the factors to keep the intermediate result
as */
/* large as possible for maximum precision. If no factor will not overflow
*/
/* the long, the largest divisor that will fit is used, in an attempt
to */
/* maintain the most digits of precision. If the smallest factor still
*/
/* over-flows the long and the smallest divisor totally zeros the number,
*/
/* the long variable type is too small for the calculation. The programmer
*/
/* must ensure that this will never happen. If the function runs out
of */
/* divisors and the next factor would still overflow the long, there
is */
/* definitely a result that is too high. If the factor loop is finished
*/
/* and the remaining divisors zero the result, then there is definitely
a */
/* result that is too low. The return code is set to OK to signify
an */
/* in-range result, using the system MAX_PAR_VALUE as the high limit
and 0 */
/* as the low limit.
*/
/*
*/
/* No more than twenty input divisors may be supplied; mallocs are not
*/
/* used due to code overhead considerations. This size limitation is
*/
/* checked when this routine is called, and also before divisors are added
*/
/* when precision is maintained.
*/
/*
*/
/*
*/
/* History: 11/02/95 - J
W: Initial Version
*/
/*
11/08/95 - J W: Use Divisors largest to smallest, Pick */
/*
out what will fit and put it in used */
/*
position, pushing the others down, do */
/*
fix of precision if it goes below three */
/*
digits.
*/
/*
11/09/95 - J W: Round up results of divisions.
*/
/*
Remove diagnostics.
*/
/*
11/15/95 - J W: Only invoke this function when all vals */
/*
are present, to avoid division by zero. */
/*
Add in CtrlMsg, the Control Mailbox */
/*
11/17/95 - J W: Do not reset the running volume every */
/*
time this processing is gone through, */
/*
because the user might stop and review */
/*
while in the middle of an infusion. */
/*
12/15/95 - J W: Make general by not specifically
*/
/*
testing for a Rate range at the end for */
/*
TOOHI.
*/
/*
12/19/95 - J W: Use MAX_PAR_VALUE rather than 99999
*/
/*
01/03/96 - J W: Don't swap divisor positions if one was */
/*
already moved down.
*/
/*
11/10/96 - J W: Renamed this function from DoseCalc to */
/*
MultDiv.
*/
/*
11/20/96 - LSO: Revised to use C-conventional 0-based */
/*
arrays.
*/
/*
03/09/97 - J W: Moved from pdose.c to optutils.c.
*/
/*
06/18/97 - J W: Increased the precision maintained
*/
/*
during calculations to three digits, */
/*
the maximum possible with our data, */
/*
using this algorithm; added detection */
/*
of two additional circumstances in */
/*
which this algorithm cannot finish: */
/*
if the precision-fix divisors overflow */
/*
the available Divisor array space, and */
/*
if illegally-large Factors would other- */
/*
wise result in an infinite loop of */
/*
the same redone precision fix.
*/
/*
06/19/97 - J W: Added a History Log message if CANTDO */
/*
has to be returned; added rounding at */
/*
first divisor trial to ensure that all */
/*
divisors possible will fit; moved the */
/*
precision-fix space retrieval to after */
/*
the place where the divisor still needs */
/*
to be remembered (previously unnoticed */
/*
bug).
*/
/*
06/24/97 - J W: Revised to ensure that the divisor
*/
/*
array will be 20 items in size by */
/*
copying the supplied data to an
*/
/*
internal Divisor array; split the */
/*
History data in case of CANTDO into 4 */
/*
cases to pinpoint the problem.
*/
/*
07/02/97 - J W: Revised not to round up when a division */
/*
gives a result of zero, which would */
/*
cause inaccurate results when digits of */
/*
precision are restored. Added more */
/*
comments to explain what might cause */
/*
the long working result to be
*/
/*
overflowed. Spotted and fixed a bug in */
/*
which digits of precision might not be */
/*
added using the correct divisor.
*/
/*
07/14/97 - J W: Revised to perform the final division */
/*
in one step and to return a *Result of */
/*
zero if returning with any return code */
/*
other than OK.
*/
/*
07/15/97 - J W: Revised the code History-logged in the */
/*
case of divisor overflow of the long */
/*
value, introduced yesterday, to a */
/*
separate one.
*/
/*
07/15/97 - J W: Revised to do the final division in
*/
/*
more than one step if all the divisors */
/*
would not fit in a long, instead of */
/*
returning a CANTDO.
*/
/*
07/16/97 - J W: Revised the description of the overflow */
/*
(0) calculation failure and wrote a */
/*
dependency note for it; revised to make */
/*
this error very unlikely if each input */
/*
factor or divisor is limited to the */
/*
absolute maximum parameter value of */
/*
9,999.
*/
/*
11/05/98 - J W: Revised to copy the Factors, too, to an */
/*
internal array in order not to disturb */
/*
the arrangement of the values input. */
/*
*/
/****************************************************************************/
int MultDiv(unsigned long *FactorsIn, int QFactors,
unsigned
long *DivisorsIn, int QDivisors, unsigned long *Result)
{
/* VARIABLES
*/
static HLE_MSG HistMsg;
/* message for History Log Entry */
unsigned long Factor[20];
/* Internal array for isolation */
unsigned long Divisor[20];
/* Internal array for isolation and */
/* guaranteed space
*/
unsigned long Temp,
/* Swap helper
*/
Saved,
/* Intermediate result saver */
TestQuo,
/* See if next fac or div will fit */
DivisorLeft,
/* Final use of remaining Divisors */
R,
/* Remainder in case of prec. fixes */
/* and for rounding elsewhere */
RR;
/* For rounding in precision fixes */
/* Array index and loop counters
*/
int I,
/* Factor use progress
*/
J,
/* Divisor use progress
*/
K,
/* Factor and Divisor searching */
H,
/* Factor and Divisor rearranging */
N;
/* Pos in Divisor array of last */
/* currently avail. Divisor. */
char FactorUsed,
/* Boolean
*/
DivisorUsed,
/* Boolean
*/
AGoodFactor;
/* Boolean
*/
/* CODE
*/
HistMsg.msgtype = MULTDIVPROCESS_TYPE;
/* Begin with Factors and Divisors sorted from largest
to smallest */
/* Copy over to the internal Factor array, doing bounds
- checking &nbssp; */
/* first.
*/
if (QFactors > 20)
{
/* "Too many factors supplied
to MultDiv"
*/
HISTLOG(MULTDIVCANTDO4_HLDAT);
*Result = 0;
return(CANTDO);
}
for (I=0; I<=QFactors-1; I++)
Factor[I] = FactorsIn[I];
/* Bubblesort
*/
for(I=QFactors; I > 1; I--)
for(J=0; J < I-1;
J++)
/* Sort from largest to smallest */
if (Factor[J]
< Factor[J+1])
{
Temp = Factor[J];
Factor[J] = Factor[J+1];
Factor[J+1] = Temp;
}
/* Copy over to the guaranteed-size internal Divisor array,
doing */
/* bounds - checking first.
*/
if (QDivisors > 20)
{
/* "Too many divisors supplied
to MultDiv"
*/
HISTLOG(MULTDIVCANTDO3_HLDAT);
*Result = 0;
return(CANTDO);
}
for (I=0; I<=QDivisors-1; I++)
Divisor[I] = DivisorsIn[I];
for(I=QDivisors; I > 1; I--)
for(J=0; J < I-1;
J++)
/* Sort from largest to smallest */
if (Divisor[J]
< Divisor[J+1])
{
Temp = Divisor[J];
Divisor[J] = Divisor[J+1];
Divisor[J+1] = Temp;
}
*Result = Factor[0];
I = 0;
/* Factor use progress
*/
J = 0;
/* Divisor use progress
*/
N = QDivisors-1;
/* in case of precision-saving */
while (I < QFactors-1)
{
TestQuo = 0xFFFFFFFF/(*Result);
FactorUsed = FALSE;
for (K=I+1; K < QFactors; K++)
/* Search for a factor to use */
{
if (Factor[K]
<= TestQuo)
{
*Result *= Factor[K];
FactorUsed = TRUE;
/* It was used, so put it in the current position and move */
/* all the rest down one to maintain large to small order */
if (K != I+1)
/* == means in current pos. already */
{
Temp = Factor[K];
for (H=K; H > I+1; H--)
{
/* Later position gets earlier one */
/* starting with the Kth
*/
Factor[H] = Factor[H-1];
}
Factor[I+1] = Temp;
}
break;
/* stop as soon as one is found */
}
}
if (!FactorUsed)
/* no Factor would fit
*/
{
/* Don't advance I
*/
/* N is
maintained as the position of the last divisor,
*/
/* precision-fix
divisors and all.
*/
if (J
> N)
/* Divide to get more room
*/
{
*Result = 0;
return(TOOHI); /* Can't
-- out of divisors &nnbsp; */
}
DivisorUsed
= FALSE;
Saved
= *Result;
for (K=J;
K <= N; K++) /* Search for a divisor to
use */
{
R = *Result % Divisor[K];
*Result /= Divisor[K];
/* Don't do any rounding right here; that's done in the
*/
/* following if block, if there is any non-fractional
*/
/* result.
*/
/* On the other hand, if there is only a fractional result, */
/* ie *Result is now zero, just use a smaller divisor. It */
/* would be possible to sacrifice precision by doing
*/
/* precision fixes for results here of 0.5 to less than 1, */
/* but that final rounding can be taken care of when no
*/
/* factors remain. It is true that if no divisor will fit */
/* here, a "CANTDO" will result, but all that means is that */
/* if only divisors larger than the largest possible
*/
/* product that will fit in a "long" are used, a "CANTDO" */
/* will result if factors still remain, otherwise a simple */
/* and accurate TOOLOW will result if no factors remain.
*/
/* Well, no. That CANTDO would be a little too easy to
*/
/* produce. Since the square root of 2^32-1 is 65535 or 6, */
/* 65536 (representing 6,554) times 65536 would overflow
*/
/* the long value, and something like 70,000 (representing */
/* 7,000) would cause *Result = 0, causing an overflow.
*/
/* But if up to twice 6554 could be accepted, that would be */
/* 13,107 (represented by 131,072) before it couldn't be
*/
/* used as a divisor, and that's beyond what the user can */
/* type into the pump because it won't fit in the display, */
/* and so it would be beyond what could be sent to this
*/
/* routine.
*/
/* Can still get the full precision fix in that case after */
/* all by simply using a precision-fix divisor of 10,000. */
if (
(*Result > 0)
||
/* Or *Result = from 1/2 up to < 1 */
(2*R >= Divisor[K])
)
{
DivisorUsed = TRUE;
/* If the result was reduced below one thousand,
*/
/* replace digits of precision using the remainder
*/
/* until the result exceeds 999. Compensate by adding */
/* to the divisors. The next factor will be guaranteed */
/* to fit, since the max factor will be no larger than */
/* 99,990.
*/
if (*Result < 1000) /* Use modulus, to do precision-fix */
{
/* out of space in Divisor Array? Have room for one */
/* more if N is less than the last index available. */
if (N < 20-1)
{
/* R = Saved % Divisor[K]; (already calculated */
/* above)
*/
/* Add a divisor at the end to make up for the */
/* extra digits added.
*/
N += 1;
if (*Result == 0)
Divisor[N] = 10000L;
else if (*Result < 10L)
/* Result has one digit
*/
Divisor[N] = 1000L;
else if (*Result < 100L)
/* Result has two digits
*/
Divisor[N] = 100L;
else
/* Result has three digits
*/
Divisor[N] = 10L;
/* Add the digits of precision back in
*/
/* Can assume remainder will never be larger */
/* than 99,990.
*/
/* Shift the remainder to the left by the added */
/* power(s) of ten;
*/
/* This should fit into a long because R is */
/* limited to less than Divisor[K], which
*/
/* should be no larger than 99,990, generally. */
R *= Divisor[N];
/* Use rounding,
*/
RR = R % Divisor[K];
/* and using rounding, reproduce the digits */
/* that go in the restored power(s) of ten. */
R /= Divisor[K];
if (2L*RR >= Divisor[K])
R += 1;
/* Shift the result to the left by the added */
/* power(s) of ten, and fill in the retained */
/* digit(s) from R.
*/
*Result = *Result * Divisor[N] + R;
}
else /*
Out of room for precision maint. */
{
/* "Working divisors overflowed array in
*/
/* MultDiv"
*/
HISTLOG(MULTDIVCANTDO2_HLDAT);
*Result = 0;
return(CANTDO);
}
/* Having done a precision fix,
*/
/* if there's nothing but precision-fix divisors */
/* remaining and no Factor will fit, then this
*/
/* algorithm cannot complete the calculation.
*/
/* Because *Result at this time will be between */
/* (inclusive) 1000 and 9,999, all factors must be */
/* limited to no larger than 0xFFFFFFFF/9999.
*/
/* If the last input (as distinct from the added, */
/* precision-fix ones) divisor has been used:
*/
if (J >= QDivisors-1)
{
TestQuo = 0xFFFFFFFF/(*Result);
AGoodFactor = FALSE;
for (H=I+1; H < QFactors; H++)
if (Factor[H] <= TestQuo)
{
AGoodFactor = TRUE;
break; /* Save a little time
*/
}
if (!AGoodFactor)
{
/* "Precision and large factor conflict in */
/* MultDiv"
*/
HISTLOG(MULTDIVCANTDO1_HLDAT);
*Result = 0;
return(CANTDO);
/* Have to return, otherwise an infinite */
/* loop would occur
*/
}
}
} /* End of if in which precision-fix was attempted
*/
/* Round the result unless precision already added
*/
else
{
R = Saved % Divisor[K];
if (2L*R >= Divisor[K])
*Result += 1;
}
/* Moved this retrieve-space operation to after where */
/* the divisor still needs to be remembered.
*/
/* If it was a precision-fix Divisor, discard the used */
/* divisor in order to fit in more precision-fix
*/
/* Divisors, in case necessary, in the limited array */
/* space.
*/
if (J > QDivisors-1) /* J is indicator, K is one used */
{
for (H=K; H < N ; H++)
{
Divisor[H] = Divisor[H+1];
}
N -= 1; /* Shift on top of
the one used */
J -= 1; /* J is incremented
below */
}
else
{
/* It was used, so put it in the current position */
if (K != J) /* == means in current pos. already */
{
Temp = Divisor[K];
for (H=K; H > J; H--)
{
/* Later position gets earlier one, */
/* starting with the Kth
*/
Divisor[H] = Divisor[H-1];
}
Divisor[J] = Temp;
}
}
break;
/* stop as soon as one is found */
}
/* End of if in which a Divisor fit */
else
/* Divisor did not fit
*/
{
*Result = Saved;
}
}
/* try another divisor
*/
/* End
of for loop to search for a Divisor that will fit
*/
if (!DivisorUsed)
/* No factor or divisor will fit */
{
/* Don't advance J
*/
/* we're stuck
*/
/* we're really stuck
*/
/* This should never happen with */
/* correct ranges of data
*/
/* Programmer failure
*/
HISTLOG(MULTDIVCANTDO0_HLDAT);
/* "Intermediate result overflows long in MultDiv"
*/
*Result = 0;
return(CANTDO);
}
else
{
/* Set position to the next divisor, but next, try again to */
J += 1;
/* multiply by any Factor that will */
/* fit.
*/
}
} /* End of if in which no factor
was used.
*/
else
I += 1;
}
/* All the remaining divisors must go into the value of
*Result at this */
/* time or else the final result will be too low.
*/
while (J<=N)
{
/* Multiply all the Divisors that
are left and put them into */
/* "DivisorLeft"; then divide
by DivisorLeft.
*/
DivisorLeft = 1L;
while (J<=N)
{
TestQuo
= 0xFFFFFFFF / DivisorLeft;
if (Divisor[J]
> TestQuo) /* Divisor won't fit in long
*/
break;
/* Divide with what is there now */
else
DivisorLeft *= Divisor[J];
J += 1;
}
/* Don't bother dividing by 1
*/
if (DivisorLeft != 1)
{
/* Use
Temp to get a modulo in order to be wary of compiler
*/
/* bugs.
Specific problem was of the form y %= (x + 1).
*/
R = *Result
% DivisorLeft;
*Result
/= DivisorLeft;
if (2*R
>= DivisorLeft)
/* The remainder involved in the division causes a round-up */
/* to the next natural number if the fraction in question */
/* is one-half or greater.
*/
*Result += 1;
if (*Result
== 0)
return(TOOLOW);
}
} /* End of while loop that breaks DivisorLeft into pieces
that fit in */
/* a long.
*/
/* No result may be larger than our largest (mostly displayable)
value */
/* of 9,999.9, which gets rounded _down_ in that case
(in the calling */
/* routine) to 9,999.0 (represented here by 99,999)
*/
if (*Result > MAX_PAR_VALUE)
{
*Result = 0;
return(TOOHI);
}
else
return(OK);
} /* End of MultDiv
*/
back
First posted Oct 30, 2003