2 * *****************************************************************************
4 * SPDX-License-Identifier: BSD-2-Clause
6 * Copyright (c) 2018-2021 Gavin D. Howard and contributors.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
11 * * Redistributions of source code must retain the above copyright notice, this
12 * list of conditions and the following disclaimer.
14 * * Redistributions in binary form must reproduce the above copyright notice,
15 * this list of conditions and the following disclaimer in the documentation
16 * and/or other materials provided with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
30 * *****************************************************************************
32 * Code for the number type.
48 // Before you try to understand this code, see the development manual
49 // (manuals/development.md#numbers).
51 static void bc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
54 * Multiply two numbers and throw a math error if they overflow.
55 * @param a The first operand.
56 * @param b The second operand.
57 * @return The product of the two operands.
59 static inline size_t bc_num_mulOverflow(size_t a, size_t b) {
61 if (BC_ERR(BC_VM_MUL_OVERFLOW(a, b, res))) bc_err(BC_ERR_MATH_OVERFLOW);
66 * Conditionally negate @a n based on @a neg. Algorithm taken from
67 * https://graphics.stanford.edu/~seander/bithacks.html#ConditionalNegate .
68 * @param n The value to turn into a signed value and negate.
69 * @param neg The condition to negate or not.
71 static inline ssize_t bc_num_neg(size_t n, bool neg) {
72 return (((ssize_t) n) ^ -((ssize_t) neg)) + neg;
76 * Compare a BcNum against zero.
77 * @param n The number to compare.
78 * @return -1 if the number is less than 0, 1 if greater, and 0 if equal.
80 ssize_t bc_num_cmpZero(const BcNum *n) {
81 return bc_num_neg((n)->len != 0, BC_NUM_NEG(n));
85 * Return the number of integer limbs in a BcNum. This is the opposite of rdx.
86 * @param n The number to return the amount of integer limbs for.
87 * @return The amount of integer limbs in @a n.
89 static inline size_t bc_num_int(const BcNum *n) {
90 return n->len ? n->len - BC_NUM_RDX_VAL(n) : 0;
94 * Expand a number's allocation capacity to at least req limbs.
95 * @param n The number to expand.
96 * @param req The number limbs to expand the allocation capacity to.
98 static void bc_num_expand(BcNum *restrict n, size_t req) {
102 req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
108 n->num = bc_vm_realloc(n->num, BC_NUM_SIZE(req));
116 * Set a number to 0 with the specified scale.
117 * @param n The number to set to zero.
118 * @param scale The scale to set the number to.
120 static void bc_num_setToZero(BcNum *restrict n, size_t scale) {
126 void bc_num_zero(BcNum *restrict n) {
127 bc_num_setToZero(n, 0);
130 void bc_num_one(BcNum *restrict n) {
137 * "Cleans" a number, which means reducing the length if the most significant
139 * @param n The number to clean.
141 static void bc_num_clean(BcNum *restrict n) {
143 // Reduce the length.
144 while (BC_NUM_NONZERO(n) && !n->num[n->len - 1]) n->len -= 1;
147 if (BC_NUM_ZERO(n)) n->rdx = 0;
150 // len must be at least as much as rdx.
151 size_t rdx = BC_NUM_RDX_VAL(n);
152 if (n->len < rdx) n->len = rdx;
157 * Returns the log base 10 of @a i. I could have done this with floating-point
158 * math, and in fact, I originally did. However, that was the only
159 * floating-point code in the entire codebase, and I decided I didn't want any.
160 * This is fast enough. Also, it might handle larger numbers better.
161 * @param i The number to return the log base 10 of.
162 * @return The log base 10 of @a i.
164 static size_t bc_num_log10(size_t i) {
166 for (len = 1; i; i /= BC_BASE, ++len);
167 assert(len - 1 <= BC_BASE_DIGS + 1);
172 * Returns the number of decimal digits in a limb that are zero starting at the
173 * most significant digits. This basically returns how much of the limb is used.
174 * @param n The number.
175 * @return The number of decimal digits that are 0 starting at the most
176 * significant digits.
178 static inline size_t bc_num_zeroDigits(const BcDig *n) {
180 assert(((size_t) *n) < BC_BASE_POW);
181 return BC_BASE_DIGS - bc_num_log10((size_t) *n);
185 * Return the total number of integer digits in a number. This is the opposite
186 * of scale, like bc_num_int() is the opposite of rdx.
187 * @param n The number.
188 * @return The number of integer digits in @a n.
190 static size_t bc_num_intDigits(const BcNum *n) {
191 size_t digits = bc_num_int(n) * BC_BASE_DIGS;
192 if (digits > 0) digits -= bc_num_zeroDigits(n->num + n->len - 1);
197 * Returns the number of limbs of a number that are non-zero starting at the
198 * most significant limbs. This expects that there are *no* integer limbs in the
199 * number because it is specifically to figure out how many zero limbs after the
200 * decimal place to ignore. If there are zero limbs after non-zero limbs, they
201 * are counted as non-zero limbs.
202 * @param n The number.
203 * @return The number of non-zero limbs after the decimal point.
205 static size_t bc_num_nonZeroLen(const BcNum *restrict n) {
206 size_t i, len = n->len;
207 assert(len == BC_NUM_RDX_VAL(n));
208 for (i = len - 1; i < len && !n->num[i]; --i);
214 * Performs a one-limb add with a carry.
215 * @param a The first limb.
216 * @param b The second limb.
217 * @param carry An in/out parameter; the carry in from the previous add and the
218 * carry out from this add.
219 * @return The resulting limb sum.
221 static BcDig bc_num_addDigits(BcDig a, BcDig b, bool *carry) {
223 assert(((BcBigDig) BC_BASE_POW) * 2 == ((BcDig) BC_BASE_POW) * 2);
224 assert(a < BC_BASE_POW);
225 assert(b < BC_BASE_POW);
228 *carry = (a >= BC_BASE_POW);
229 if (*carry) a -= BC_BASE_POW;
232 assert(a < BC_BASE_POW);
238 * Performs a one-limb subtract with a carry.
239 * @param a The first limb.
240 * @param b The second limb.
241 * @param carry An in/out parameter; the carry in from the previous subtract
242 * and the carry out from this subtract.
243 * @return The resulting limb difference.
245 static BcDig bc_num_subDigits(BcDig a, BcDig b, bool *carry) {
247 assert(a < BC_BASE_POW);
248 assert(b < BC_BASE_POW);
252 if (*carry) a += BC_BASE_POW;
255 assert(a - b < BC_BASE_POW);
261 * Add two BcDig arrays and store the result in the first array.
262 * @param a The first operand and out array.
263 * @param b The second operand.
264 * @param len The length of @a b.
266 static void bc_num_addArrays(BcDig *restrict a, const BcDig *restrict b,
272 for (i = 0; i < len; ++i) a[i] = bc_num_addDigits(a[i], b[i], &carry);
274 // Take care of the extra limbs in the bigger array.
275 for (; carry; ++i) a[i] = bc_num_addDigits(a[i], 0, &carry);
279 * Subtract two BcDig arrays and store the result in the first array.
280 * @param a The first operand and out array.
281 * @param b The second operand.
282 * @param len The length of @a b.
284 static void bc_num_subArrays(BcDig *restrict a, const BcDig *restrict b,
290 for (i = 0; i < len; ++i) a[i] = bc_num_subDigits(a[i], b[i], &carry);
292 // Take care of the extra limbs in the bigger array.
293 for (; carry; ++i) a[i] = bc_num_subDigits(a[i], 0, &carry);
297 * Multiply a BcNum array by a one-limb number. This is a faster version of
298 * multiplication for when we can use it.
299 * @param a The BcNum to multiply by the one-limb number.
300 * @param b The one limb of the one-limb number.
301 * @param c The return parameter.
303 static void bc_num_mulArray(const BcNum *restrict a, BcBigDig b,
309 assert(b <= BC_BASE_POW);
311 // Make sure the return parameter is big enough.
312 if (a->len + 1 > c->cap) bc_num_expand(c, a->len + 1);
314 // We want the entire return parameter to be zero for cleaning later.
315 memset(c->num, 0, BC_NUM_SIZE(c->cap));
317 // Actual multiplication loop.
318 for (i = 0; i < a->len; ++i) {
319 BcBigDig in = ((BcBigDig) a->num[i]) * b + carry;
320 c->num[i] = in % BC_BASE_POW;
321 carry = in / BC_BASE_POW;
324 assert(carry < BC_BASE_POW);
326 // Finishing touches.
327 c->num[i] = (BcDig) carry;
329 c->len += (carry != 0);
334 assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
335 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
336 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);
340 * Divide a BcNum array by a one-limb number. This is a faster version of divide
341 * for when we can use it.
342 * @param a The BcNum to multiply by the one-limb number.
343 * @param b The one limb of the one-limb number.
344 * @param c The return parameter for the quotient.
345 * @param rem The return parameter for the remainder.
347 static void bc_num_divArray(const BcNum *restrict a, BcBigDig b,
348 BcNum *restrict c, BcBigDig *rem)
353 assert(c->cap >= a->len);
355 // Actual division loop.
356 for (i = a->len - 1; i < a->len; --i) {
357 BcBigDig in = ((BcBigDig) a->num[i]) + carry * BC_BASE_POW;
358 assert(in / b < BC_BASE_POW);
359 c->num[i] = (BcDig) (in / b);
363 // Finishing touches.
369 assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
370 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
371 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);
375 * Compare two BcDig arrays and return >0 if @a b is greater, <0 if @a b is
376 * less, and 0 if equal. Both @a a and @a b must have the same length.
377 * @param a The first array.
378 * @param b The second array.
379 * @param len The minimum length of the arrays.
381 static ssize_t bc_num_compare(const BcDig *restrict a, const BcDig *restrict b,
386 for (i = len - 1; i < len && !(c = a[i] - b[i]); --i);
387 return bc_num_neg(i + 1, c < 0);
390 ssize_t bc_num_cmp(const BcNum *a, const BcNum *b) {
392 size_t i, min, a_int, b_int, diff, ardx, brdx;
393 BcDig *max_num, *min_num;
394 bool a_max, neg = false;
397 assert(a != NULL && b != NULL);
400 if (a == b) return 0;
403 if (BC_NUM_ZERO(a)) return bc_num_neg(b->len != 0, !BC_NUM_NEG(b));
404 if (BC_NUM_ZERO(b)) return bc_num_cmpZero(a);
406 if (BC_NUM_NEG(b)) neg = true;
409 else if (BC_NUM_NEG(b)) return 1;
411 // Get the number of int limbs in each number and get the difference.
412 a_int = bc_num_int(a);
413 b_int = bc_num_int(b);
416 // If there's a difference, then just return the comparison.
417 if (a_int) return neg ? -((ssize_t) a_int) : (ssize_t) a_int;
419 // Get the rdx's and figure out the max.
420 ardx = BC_NUM_RDX_VAL(a);
421 brdx = BC_NUM_RDX_VAL(b);
422 a_max = (ardx > brdx);
424 // Set variables based on the above.
428 max_num = a->num + diff;
434 max_num = b->num + diff;
438 // Do a full limb-by-limb comparison.
439 cmp = bc_num_compare(max_num, min_num, b_int + min);
441 // If we found a difference, return it based on state.
442 if (cmp) return bc_num_neg((size_t) cmp, !a_max == !neg);
444 // If there was no difference, then the final step is to check which number
445 // has greater or lesser limbs beyond the other's.
446 for (max_num -= diff, i = diff - 1; i < diff; --i) {
447 if (max_num[i]) return bc_num_neg(1, !a_max == !neg);
453 void bc_num_truncate(BcNum *restrict n, size_t places) {
455 size_t nrdx, places_rdx;
459 // Grab these needed values; places_rdx is the rdx equivalent to places like
461 nrdx = BC_NUM_RDX_VAL(n);
462 places_rdx = nrdx ? nrdx - BC_NUM_RDX(n->scale - places) : 0;
464 // We cannot truncate more places than we have.
465 assert(places <= n->scale && (BC_NUM_ZERO(n) || places_rdx <= n->len));
468 BC_NUM_RDX_SET(n, nrdx - places_rdx);
470 // Only when the number is nonzero do we need to do the hard stuff.
471 if (BC_NUM_NONZERO(n)) {
475 // This calculates how many decimal digits are in the least significant
477 pow = n->scale % BC_BASE_DIGS;
478 pow = pow ? BC_BASE_DIGS - pow : 0;
479 pow = bc_num_pow10[pow];
481 n->len -= places_rdx;
483 // We have to move limbs to maintain invariants. The limbs must begin at
484 // the beginning of the BcNum array.
485 memmove(n->num, n->num + places_rdx, BC_NUM_SIZE(n->len));
487 // Clear the lower part of the last digit.
488 if (BC_NUM_NONZERO(n)) n->num[0] -= n->num[0] % (BcDig) pow;
494 void bc_num_extend(BcNum *restrict n, size_t places) {
496 size_t nrdx, places_rdx;
500 // Easy case with zero; set the scale.
501 if (BC_NUM_ZERO(n)) {
506 // Grab these needed values; places_rdx is the rdx equivalent to places like
508 nrdx = BC_NUM_RDX_VAL(n);
509 places_rdx = BC_NUM_RDX(places + n->scale) - nrdx;
511 // This is the hard case. We need to expand the number, move the limbs, and
512 // set the limbs that were just cleared.
514 bc_num_expand(n, bc_vm_growSize(n->len, places_rdx));
515 memmove(n->num + places_rdx, n->num, BC_NUM_SIZE(n->len));
516 memset(n->num, 0, BC_NUM_SIZE(places_rdx));
519 // Finally, set scale and rdx.
520 BC_NUM_RDX_SET(n, nrdx + places_rdx);
522 n->len += places_rdx;
524 assert(BC_NUM_RDX_VAL(n) == BC_NUM_RDX(n->scale));
528 * Retires (finishes) a multiplication or division operation.
530 static void bc_num_retireMul(BcNum *restrict n, size_t scale,
531 bool neg1, bool neg2)
533 // Make sure scale is correct.
534 if (n->scale < scale) bc_num_extend(n, scale - n->scale);
535 else bc_num_truncate(n, n->scale - scale);
539 // We need to ensure rdx is correct.
540 if (BC_NUM_NONZERO(n)) n->rdx = BC_NUM_NEG_VAL(n, !neg1 != !neg2);
544 * Splits a number into two BcNum's. This is used in Karatsuba.
545 * @param n The number to split.
546 * @param idx The index to split at.
547 * @param a An out parameter; the low part of @a n.
548 * @param b An out parameter; the high part of @a n.
550 static void bc_num_split(const BcNum *restrict n, size_t idx,
551 BcNum *restrict a, BcNum *restrict b)
553 // We want a and b to be clear.
554 assert(BC_NUM_ZERO(a));
555 assert(BC_NUM_ZERO(b));
560 // Set the fields first.
561 b->len = n->len - idx;
563 a->scale = b->scale = 0;
564 BC_NUM_RDX_SET(a, 0);
565 BC_NUM_RDX_SET(b, 0);
567 assert(a->cap >= a->len);
568 assert(b->cap >= b->len);
570 // Copy the arrays. This is not necessary for safety, but it is faster,
572 memcpy(b->num, n->num + idx, BC_NUM_SIZE(b->len));
573 memcpy(a->num, n->num, BC_NUM_SIZE(idx));
577 // If the index is weird, just skip the split.
578 else bc_num_copy(a, n);
584 * Copies a number into another, but shifts the rdx so that the result number
585 * only sees the integer part of the source number.
586 * @param n The number to copy.
587 * @param r The result number with a shifted rdx, len, and num.
589 static void bc_num_shiftRdx(const BcNum *restrict n, BcNum *restrict r) {
591 size_t rdx = BC_NUM_RDX_VAL(n);
593 r->len = n->len - rdx;
594 r->cap = n->cap - rdx;
595 r->num = n->num + rdx;
597 BC_NUM_RDX_SET_NEG(r, 0, BC_NUM_NEG(n));
602 * Shifts a number so that all of the least significant limbs of the number are
603 * skipped. This must be undone by bc_num_unshiftZero().
604 * @param n The number to shift.
606 static size_t bc_num_shiftZero(BcNum *restrict n) {
610 // If we don't have an integer, that is a problem, but it's also a bug
611 // because the caller should have set everything up right.
612 assert(!BC_NUM_RDX_VAL(n) || BC_NUM_ZERO(n));
614 for (i = 0; i < n->len && !n->num[i]; ++i);
623 * Undo the damage done by bc_num_unshiftZero(). This must be called like all
624 * cleanup functions: after a label used by setjmp() and longjmp().
625 * @param n The number to unshift.
626 * @param places_rdx The amount the number was originally shift.
628 static void bc_num_unshiftZero(BcNum *restrict n, size_t places_rdx) {
629 n->len += places_rdx;
630 n->num -= places_rdx;
634 * Shifts the digits right within a number by no more than BC_BASE_DIGS - 1.
635 * This is the final step on shifting numbers with the shift operators. It
636 * depends on the caller to shift the limbs properly because all it does is
637 * ensure that the rdx point is realigned to be between limbs.
638 * @param n The number to shift digits in.
639 * @param dig The number of places to shift right.
641 static void bc_num_shift(BcNum *restrict n, BcBigDig dig) {
643 size_t i, len = n->len;
644 BcBigDig carry = 0, pow;
647 assert(dig < BC_BASE_DIGS);
649 // Figure out the parameters for division.
650 pow = bc_num_pow10[dig];
651 dig = bc_num_pow10[BC_BASE_DIGS - dig];
653 // Run a series of divisions and mods with carries across the entire number
654 // array. This effectively shifts everything over.
655 for (i = len - 1; i < len; --i) {
657 in = ((BcBigDig) ptr[i]);
660 ptr[i] = ((BcDig) (in / pow)) + (BcDig) temp;
667 * Shift a number left by a certain number of places. This is the workhorse of
668 * the left shift operator.
669 * @param n The number to shift left.
670 * @param places The amount of places to shift @a n left by.
672 static void bc_num_shiftLeft(BcNum *restrict n, size_t places) {
680 // Make sure to grow the number if necessary.
681 if (places > n->scale) {
682 size_t size = bc_vm_growSize(BC_NUM_RDX(places - n->scale), n->len);
683 if (size > SIZE_MAX - 1) bc_err(BC_ERR_MATH_OVERFLOW);
686 // If zero, we can just set the scale and bail.
687 if (BC_NUM_ZERO(n)) {
688 if (n->scale >= places) n->scale -= places;
693 // When I changed bc to have multiple digits per limb, this was the hardest
694 // code to change. This and shift right. Make sure you understand this
695 // before attempting anything.
697 // This is how many limbs we will shift.
698 dig = (BcBigDig) (places % BC_BASE_DIGS);
701 // Convert places to a rdx value.
702 places_rdx = BC_NUM_RDX(places);
704 // If the number is not an integer, we need special care. The reason an
705 // integer doesn't is because left shift would only extend the integer,
706 // whereas a non-integer might have its fractional part eliminated or only
707 // partially eliminated.
710 size_t nrdx = BC_NUM_RDX_VAL(n);
712 // If the number's rdx is bigger, that's the hard case.
713 if (nrdx >= places_rdx) {
715 size_t mod = n->scale % BC_BASE_DIGS, revdig;
717 // We want mod to be in the range [1, BC_BASE_DIGS], not
718 // [0, BC_BASE_DIGS).
719 mod = mod ? mod : BC_BASE_DIGS;
721 // We need to reverse dig to get the actual number of digits.
722 revdig = dig ? BC_BASE_DIGS - dig : 0;
724 // If the two overflow BC_BASE_DIGS, we need to move an extra place.
725 if (mod + revdig > BC_BASE_DIGS) places_rdx = 1;
728 else places_rdx -= nrdx;
731 // If this is non-zero, we need an extra place, so expand, move, and set.
733 bc_num_expand(n, bc_vm_growSize(n->len, places_rdx));
734 memmove(n->num + places_rdx, n->num, BC_NUM_SIZE(n->len));
735 memset(n->num, 0, BC_NUM_SIZE(places_rdx));
736 n->len += places_rdx;
739 // Set the scale appropriately.
740 if (places > n->scale) {
742 BC_NUM_RDX_SET(n, 0);
746 BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale));
749 // Finally, shift within limbs.
750 if (shift) bc_num_shift(n, BC_BASE_DIGS - dig);
755 void bc_num_shiftRight(BcNum *restrict n, size_t places) {
758 size_t places_rdx, scale, scale_mod, int_len, expand;
763 // If zero, we can just set the scale and bail.
764 if (BC_NUM_ZERO(n)) {
766 bc_num_expand(n, BC_NUM_RDX(n->scale));
770 // Amount within a limb we have to shift by.
771 dig = (BcBigDig) (places % BC_BASE_DIGS);
776 // Figure out how the scale is affected.
777 scale_mod = scale % BC_BASE_DIGS;
778 scale_mod = scale_mod ? scale_mod : BC_BASE_DIGS;
780 // We need to know the int length and rdx for places.
781 int_len = bc_num_int(n);
782 places_rdx = BC_NUM_RDX(places);
784 // If we are going to shift past a limb boundary or not, set accordingly.
785 if (scale_mod + dig > BC_BASE_DIGS) {
786 expand = places_rdx - 1;
795 if (expand > int_len) expand -= int_len;
798 // Extend, expand, and zero.
799 bc_num_extend(n, places_rdx * BC_BASE_DIGS);
800 bc_num_expand(n, bc_vm_growSize(expand, n->len));
801 memset(n->num + n->len, 0, BC_NUM_SIZE(expand));
806 BC_NUM_RDX_SET(n, 0);
808 // Finally, shift within limbs.
809 if (shift) bc_num_shift(n, dig);
811 n->scale = scale + places;
812 BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale));
816 assert(BC_NUM_RDX_VAL(n) <= n->len && n->len <= n->cap);
817 assert(BC_NUM_RDX_VAL(n) == BC_NUM_RDX(n->scale));
821 * Invert @a into @a b at the current scale.
822 * @param a The number to invert.
823 * @param b The return parameter. This must be preallocated.
824 * @param scale The current scale.
826 static inline void bc_num_inv(BcNum *a, BcNum *b, size_t scale) {
827 assert(BC_NUM_NONZERO(a));
828 bc_num_div(&vm.one, a, b, scale);
832 * Tests if a number is a integer with scale or not. Returns true if the number
833 * is not an integer. If it is, its integer shifted form is copied into the
834 * result parameter for use where only integers are allowed.
835 * @param n The integer to test and shift.
836 * @param r The number to store the shifted result into. This number should
837 * *not* be allocated.
838 * @return True if the number is a non-integer, false otherwise.
840 static bool bc_num_nonInt(const BcNum *restrict n, BcNum *restrict r) {
843 size_t i, rdx = BC_NUM_RDX_VAL(n);
846 memcpy(r, n, sizeof(BcNum));
852 for (i = 0; zero && i < rdx; ++i) zero = (n->num[i] == 0);
854 if (BC_ERR(!zero)) return true;
856 bc_num_shiftRdx(n, r);
861 #if BC_ENABLE_EXTRA_MATH
864 * Execute common code for an operater that needs an integer for the second
865 * operand and return the integer operand as a BcBigDig.
866 * @param a The first operand.
867 * @param b The second operand.
868 * @param c The result operand.
869 * @return The second operand as a hardware integer.
871 static BcBigDig bc_num_intop(const BcNum *a, const BcNum *b, BcNum *restrict c)
875 if (BC_ERR(bc_num_nonInt(b, &temp))) bc_err(BC_ERR_MATH_NON_INTEGER);
879 return bc_num_bigdig(&temp);
881 #endif // BC_ENABLE_EXTRA_MATH
884 * This is the actual implementation of add *and* subtract. Since this function
885 * doesn't need to use scale (per the bc spec), I am hijacking it to say whether
886 * it's doing an add or a subtract. And then I convert substraction to addition
887 * of negative second operand. This is a BcNumBinOp function.
888 * @param a The first operand.
889 * @param b The second operand.
890 * @param c The return parameter.
891 * @param sub Non-zero for a subtract, zero for an add.
893 static void bc_num_as(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub) {
895 BcDig *ptr_c, *ptr_l, *ptr_r;
896 size_t i, min_rdx, max_rdx, diff, a_int, b_int, min_len, max_len, max_int;
897 size_t len_l, len_r, ardx, brdx;
898 bool b_neg, do_sub, do_rev_sub, carry, c_neg;
900 if (BC_NUM_ZERO(b)) {
905 if (BC_NUM_ZERO(a)) {
907 c->rdx = BC_NUM_NEG_VAL(c, BC_NUM_NEG(b) != sub);
911 // Invert sign of b if it is to be subtracted. This operation must
912 // precede the tests for any of the operands being zero.
913 b_neg = (BC_NUM_NEG(b) != sub);
915 // Figure out if we will actually add the numbers if their signs are equal
917 do_sub = (BC_NUM_NEG(a) != b_neg);
919 a_int = bc_num_int(a);
920 b_int = bc_num_int(b);
921 max_int = BC_MAX(a_int, b_int);
923 // Figure out which number will have its last limbs copied (for addition) or
924 // subtracted (for subtraction).
925 ardx = BC_NUM_RDX_VAL(a);
926 brdx = BC_NUM_RDX_VAL(b);
927 min_rdx = BC_MIN(ardx, brdx);
928 max_rdx = BC_MAX(ardx, brdx);
929 diff = max_rdx - min_rdx;
931 max_len = max_int + max_rdx;
935 // Check whether b has to be subtracted from a or a from b.
936 if (a_int != b_int) do_rev_sub = (a_int < b_int);
937 else if (ardx > brdx)
938 do_rev_sub = (bc_num_compare(a->num + diff, b->num, b->len) < 0);
940 do_rev_sub = (bc_num_compare(a->num, b->num + diff, a->len) <= 0);
944 // The result array of the addition might come out one element
945 // longer than the bigger of the operand arrays.
947 do_rev_sub = (a_int < b_int);
950 assert(max_len <= c->cap);
952 // Cache values for simple code later.
969 // This is true if the numbers have a different number of limbs after the
973 // If the rdx values of the operands do not match, the result will
974 // have low end elements that are the positive or negative trailing
975 // elements of the operand with higher rdx value.
976 if ((ardx > brdx) != do_rev_sub) {
978 // !do_rev_sub && ardx > brdx || do_rev_sub && brdx > ardx
979 // The left operand has BcDig values that need to be copied,
980 // either from a or from b (in case of a reversed subtraction).
981 memcpy(ptr_c, ptr_l, BC_NUM_SIZE(diff));
987 // The right operand has BcDig values that need to be copied
988 // or subtracted from zero (in case of a subtraction).
991 // do_sub (do_rev_sub && ardx > brdx ||
992 // !do_rev_sub && brdx > ardx)
993 for (i = 0; i < diff; i++)
994 ptr_c[i] = bc_num_subDigits(0, ptr_r[i], &carry);
998 // !do_sub && brdx > ardx
999 memcpy(ptr_c, ptr_r, BC_NUM_SIZE(diff));
1002 // Future code needs to ignore the limbs we just did.
1007 // The return value pointer needs to ignore what we just did.
1011 // This is the length that can be directly added/subtracted.
1012 min_len = BC_MIN(len_l, len_r);
1014 // After dealing with possible low array elements that depend on only one
1015 // operand above, the actual add or subtract can be performed as if the rdx
1016 // of both operands was the same.
1018 // Inlining takes care of eliminating constant zero arguments to
1019 // addDigit/subDigit (checked in disassembly of resulting bc binary
1020 // compiled with gcc and clang).
1023 // Actual subtraction.
1024 for (i = 0; i < min_len; ++i)
1025 ptr_c[i] = bc_num_subDigits(ptr_l[i], ptr_r[i], &carry);
1027 // Finishing the limbs beyond the direct subtraction.
1028 for (; i < len_l; ++i) ptr_c[i] = bc_num_subDigits(ptr_l[i], 0, &carry);
1033 for (i = 0; i < min_len; ++i)
1034 ptr_c[i] = bc_num_addDigits(ptr_l[i], ptr_r[i], &carry);
1036 // Finishing the limbs beyond the direct addition.
1037 for (; i < len_l; ++i) ptr_c[i] = bc_num_addDigits(ptr_l[i], 0, &carry);
1039 // Addition can create an extra limb. We take care of that here.
1040 ptr_c[i] = bc_num_addDigits(0, 0, &carry);
1043 assert(carry == false);
1045 // The result has the same sign as a, unless the operation was a
1046 // reverse subtraction (b - a).
1047 c_neg = BC_NUM_NEG(a) != (do_sub && do_rev_sub);
1048 BC_NUM_RDX_SET_NEG(c, max_rdx, c_neg);
1050 c->scale = BC_MAX(a->scale, b->scale);
1056 * The simple multiplication that karatsuba dishes out to when the length of the
1057 * numbers gets low enough. This doesn't use scale because it treats the
1058 * operands as though they are integers.
1059 * @param a The first operand.
1060 * @param b The second operand.
1061 * @param c The return parameter.
1063 static void bc_num_m_simp(const BcNum *a, const BcNum *b, BcNum *restrict c) {
1065 size_t i, alen = a->len, blen = b->len, clen;
1066 BcDig *ptr_a = a->num, *ptr_b = b->num, *ptr_c;
1067 BcBigDig sum = 0, carry = 0;
1069 assert(sizeof(sum) >= sizeof(BcDig) * 2);
1070 assert(!BC_NUM_RDX_VAL(a) && !BC_NUM_RDX_VAL(b));
1072 // Make sure c is big enough.
1073 clen = bc_vm_growSize(alen, blen);
1074 bc_num_expand(c, bc_vm_growSize(clen, 1));
1076 // If we don't memset, then we might have uninitialized data use later.
1078 memset(ptr_c, 0, BC_NUM_SIZE(c->cap));
1080 // This is the actual multiplication loop. It uses the lattice form of long
1081 // multiplication (see the explanation on the web page at
1082 // https://knilt.arcc.albany.edu/What_is_Lattice_Multiplication or the
1083 // explanation at Wikipedia).
1084 for (i = 0; i < clen; ++i) {
1086 ssize_t sidx = (ssize_t) (i - blen + 1);
1089 // These are the start indices.
1090 j = (size_t) BC_MAX(0, sidx);
1091 k = BC_MIN(i, blen - 1);
1093 // On every iteration of this loop, a multiplication happens, then the
1094 // sum is automatically calculated.
1095 for (; j < alen && k < blen; ++j, --k) {
1097 sum += ((BcBigDig) ptr_a[j]) * ((BcBigDig) ptr_b[k]);
1099 if (sum >= ((BcBigDig) BC_BASE_POW) * BC_BASE_POW) {
1100 carry += sum / BC_BASE_POW;
1105 // Calculate the carry.
1106 if (sum >= BC_BASE_POW) {
1107 carry += sum / BC_BASE_POW;
1111 // Store and set up for next iteration.
1112 ptr_c[i] = (BcDig) sum;
1113 assert(ptr_c[i] < BC_BASE_POW);
1118 // This should always be true because there should be no carry on the last
1119 // digit; multiplication never goes above the sum of both lengths.
1126 * Does a shifted add or subtract for Karatsuba below. This calls either
1127 * bc_num_addArrays() or bc_num_subArrays().
1128 * @param n An in/out parameter; the first operand and return parameter.
1129 * @param a The second operand.
1130 * @param shift The amount to shift @a n by when adding/subtracting.
1131 * @param op The function to call, either bc_num_addArrays() or
1132 * bc_num_subArrays().
1134 static void bc_num_shiftAddSub(BcNum *restrict n, const BcNum *restrict a,
1135 size_t shift, BcNumShiftAddOp op)
1137 assert(n->len >= shift + a->len);
1138 assert(!BC_NUM_RDX_VAL(n) && !BC_NUM_RDX_VAL(a));
1139 op(n->num + shift, a->num, a->len);
1143 * Implements the Karatsuba algorithm.
1145 static void bc_num_k(const BcNum *a, const BcNum *b, BcNum *restrict c) {
1147 size_t max, max2, total;
1148 BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp;
1149 BcDig *digs, *dig_ptr;
1151 bool aone = BC_NUM_ONE(a);
1153 assert(BC_NUM_ZERO(c));
1155 if (BC_NUM_ZERO(a) || BC_NUM_ZERO(b)) return;
1157 if (aone || BC_NUM_ONE(b)) {
1158 bc_num_copy(c, aone ? b : a);
1159 if ((aone && BC_NUM_NEG(a)) || BC_NUM_NEG(b)) BC_NUM_NEG_TGL(c);
1163 // Shell out to the simple algorithm with certain conditions.
1164 if (a->len < BC_NUM_KARATSUBA_LEN || b->len < BC_NUM_KARATSUBA_LEN) {
1165 bc_num_m_simp(a, b, c);
1169 // We need to calculate the max size of the numbers that can result from the
1171 max = BC_MAX(a->len, b->len);
1172 max = BC_MAX(max, BC_NUM_DEF_SIZE);
1173 max2 = (max + 1) / 2;
1175 // Calculate the space needed for all of the temporary allocations. We do
1176 // this to just allocate once.
1177 total = bc_vm_arraySize(BC_NUM_KARATSUBA_ALLOCS, max);
1181 // Allocate space for all of the temporaries.
1182 digs = dig_ptr = bc_vm_malloc(BC_NUM_SIZE(total));
1184 // Set up the temporaries.
1185 bc_num_setup(&l1, dig_ptr, max);
1187 bc_num_setup(&h1, dig_ptr, max);
1189 bc_num_setup(&l2, dig_ptr, max);
1191 bc_num_setup(&h2, dig_ptr, max);
1193 bc_num_setup(&m1, dig_ptr, max);
1195 bc_num_setup(&m2, dig_ptr, max);
1197 // Some temporaries need the ability to grow, so we allocate them
1199 max = bc_vm_growSize(max, 1);
1200 bc_num_init(&z0, max);
1201 bc_num_init(&z1, max);
1202 bc_num_init(&z2, max);
1203 max = bc_vm_growSize(max, max) + 1;
1204 bc_num_init(&temp, max);
1206 BC_SETJMP_LOCKED(err);
1211 bc_num_expand(c, max);
1213 memset(c->num, 0, BC_NUM_SIZE(c->len));
1215 // Split the parameters.
1216 bc_num_split(a, max2, &l1, &h1);
1217 bc_num_split(b, max2, &l2, &h2);
1219 // Do the subtraction.
1220 bc_num_sub(&h1, &l1, &m1, 0);
1221 bc_num_sub(&l2, &h2, &m2, 0);
1223 // The if statements below are there for efficiency reasons. The best way to
1224 // understand them is to understand the Karatsuba algorithm because now that
1225 // the ollocations and splits are done, the algorithm is pretty
1228 if (BC_NUM_NONZERO(&h1) && BC_NUM_NONZERO(&h2)) {
1230 assert(BC_NUM_RDX_VALID_NP(h1));
1231 assert(BC_NUM_RDX_VALID_NP(h2));
1233 bc_num_m(&h1, &h2, &z2, 0);
1236 bc_num_shiftAddSub(c, &z2, max2 * 2, bc_num_addArrays);
1237 bc_num_shiftAddSub(c, &z2, max2, bc_num_addArrays);
1240 if (BC_NUM_NONZERO(&l1) && BC_NUM_NONZERO(&l2)) {
1242 assert(BC_NUM_RDX_VALID_NP(l1));
1243 assert(BC_NUM_RDX_VALID_NP(l2));
1245 bc_num_m(&l1, &l2, &z0, 0);
1248 bc_num_shiftAddSub(c, &z0, max2, bc_num_addArrays);
1249 bc_num_shiftAddSub(c, &z0, 0, bc_num_addArrays);
1252 if (BC_NUM_NONZERO(&m1) && BC_NUM_NONZERO(&m2)) {
1254 assert(BC_NUM_RDX_VALID_NP(m1));
1255 assert(BC_NUM_RDX_VALID_NP(m1));
1257 bc_num_m(&m1, &m2, &z1, 0);
1260 op = (BC_NUM_NEG_NP(m1) != BC_NUM_NEG_NP(m2)) ?
1261 bc_num_subArrays : bc_num_addArrays;
1262 bc_num_shiftAddSub(c, &z1, max2, op);
1276 * Does checks for Karatsuba. It also changes things to ensure that the
1277 * Karatsuba and simple multiplication can treat the numbers as integers. This
1278 * is a BcNumBinOp function.
1279 * @param a The first operand.
1280 * @param b The second operand.
1281 * @param c The return parameter.
1282 * @param scale The current scale.
1284 static void bc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) {
1287 size_t ascale, bscale, ardx, brdx, azero = 0, bzero = 0, zero, len, rscale;
1289 assert(BC_NUM_RDX_VALID(a));
1290 assert(BC_NUM_RDX_VALID(b));
1297 // This sets the final scale according to the bc spec.
1298 scale = BC_MAX(scale, ascale);
1299 scale = BC_MAX(scale, bscale);
1300 rscale = ascale + bscale;
1301 scale = BC_MIN(rscale, scale);
1303 // If this condition is true, we can use bc_num_mulArray(), which would be
1305 if ((a->len == 1 || b->len == 1) && !a->rdx && !b->rdx) {
1310 // Set the correct operands.
1312 dig = (BcBigDig) a->num[0];
1316 dig = (BcBigDig) b->num[0];
1320 bc_num_mulArray(operand, dig, c);
1322 // Need to make sure the sign is correct.
1323 if (BC_NUM_NONZERO(c))
1324 c->rdx = BC_NUM_NEG_VAL(c, BC_NUM_NEG(a) != BC_NUM_NEG(b));
1329 assert(BC_NUM_RDX_VALID(a));
1330 assert(BC_NUM_RDX_VALID(b));
1334 // We need copies because of all of the mutation needed to make Karatsuba
1335 // think the numbers are integers.
1336 bc_num_init(&cpa, a->len + BC_NUM_RDX_VAL(a));
1337 bc_num_init(&cpb, b->len + BC_NUM_RDX_VAL(b));
1339 BC_SETJMP_LOCKED(err);
1343 bc_num_copy(&cpa, a);
1344 bc_num_copy(&cpb, b);
1346 assert(BC_NUM_RDX_VALID_NP(cpa));
1347 assert(BC_NUM_RDX_VALID_NP(cpb));
1349 BC_NUM_NEG_CLR_NP(cpa);
1350 BC_NUM_NEG_CLR_NP(cpb);
1352 assert(BC_NUM_RDX_VALID_NP(cpa));
1353 assert(BC_NUM_RDX_VALID_NP(cpb));
1355 // These are what makes them appear like integers.
1356 ardx = BC_NUM_RDX_VAL_NP(cpa) * BC_BASE_DIGS;
1357 bc_num_shiftLeft(&cpa, ardx);
1359 brdx = BC_NUM_RDX_VAL_NP(cpb) * BC_BASE_DIGS;
1360 bc_num_shiftLeft(&cpb, brdx);
1362 // We need to reset the jump here because azero and bzero are used in the
1363 // cleanup, and local variables are not guaranteed to be the same after a
1369 // We want to ignore zero limbs.
1370 azero = bc_num_shiftZero(&cpa);
1371 bzero = bc_num_shiftZero(&cpb);
1373 BC_SETJMP_LOCKED(err);
1380 bc_num_k(&cpa, &cpb, c);
1382 // The return parameter needs to have its scale set. This is the start. It
1383 // also needs to be shifted by the same amount as a and b have limbs after
1384 // the decimal point.
1385 zero = bc_vm_growSize(azero, bzero);
1386 len = bc_vm_growSize(c->len, zero);
1388 bc_num_expand(c, len);
1390 // Shift c based on the limbs after the decimal point in a and b.
1391 bc_num_shiftLeft(c, (len - c->len) * BC_BASE_DIGS);
1392 bc_num_shiftRight(c, ardx + brdx);
1394 bc_num_retireMul(c, scale, BC_NUM_NEG(a), BC_NUM_NEG(b));
1398 bc_num_unshiftZero(&cpb, bzero);
1400 bc_num_unshiftZero(&cpa, azero);
1406 * Returns true if the BcDig array has non-zero limbs, false otherwise.
1407 * @param a The array to test.
1408 * @param len The length of the array.
1409 * @return True if @a has any non-zero limbs, false otherwise.
1411 static bool bc_num_nonZeroDig(BcDig *restrict a, size_t len) {
1413 bool nonzero = false;
1414 for (i = len - 1; !nonzero && i < len; --i) nonzero = (a[i] != 0);
1419 * Compares a BcDig array against a BcNum. This is especially suited for
1420 * division. Returns >0 if @a a is greater than @a b, <0 if it is less, and =0
1421 * if they are equal.
1422 * @param a The array.
1423 * @param b The number.
1424 * @param len The length to assume the arrays are. This is always less than the
1425 * actual length because of how this is implemented.
1427 static ssize_t bc_num_divCmp(const BcDig *a, const BcNum *b, size_t len) {
1431 if (b->len > len && a[len]) cmp = bc_num_compare(a, b->num, len + 1);
1432 else if (b->len <= len) {
1433 if (a[len]) cmp = 1;
1434 else cmp = bc_num_compare(a, b->num, len);
1442 * Extends the two operands of a division by BC_BASE_DIGS minus the number of
1443 * digits in the divisor estimate. In other words, it is shifting the numbers in
1444 * order to force the divisor estimate to fill the limb.
1445 * @param a The first operand.
1446 * @param b The second operand.
1447 * @param divisor The divisor estimate.
1449 static void bc_num_divExtend(BcNum *restrict a, BcNum *restrict b,
1454 assert(divisor < BC_BASE_POW);
1456 pow = BC_BASE_DIGS - bc_num_log10((size_t) divisor);
1458 bc_num_shiftLeft(a, pow);
1459 bc_num_shiftLeft(b, pow);
1463 * Actually does division. This is a rewrite of my original code by Stefan Esser
1465 * @param a The first operand.
1466 * @param b The second operand.
1467 * @param c The return parameter.
1468 * @param scale The current scale.
1470 static void bc_num_d_long(BcNum *restrict a, BcNum *restrict b,
1471 BcNum *restrict c, size_t scale)
1474 size_t len, end, i, rdx;
1476 bool nonzero = false;
1478 assert(b->len < a->len);
1485 // This is a final time to make sure c is big enough and that its array is
1487 bc_num_expand(c, a->len);
1488 memset(c->num, 0, c->cap * sizeof(BcDig));
1491 BC_NUM_RDX_SET(c, BC_NUM_RDX_VAL(a));
1492 c->scale = a->scale;
1495 // This is pulling the most significant limb of b in order to establish a
1496 // good "estimate" for the actual divisor.
1497 divisor = (BcBigDig) b->num[len - 1];
1499 // The entire bit of code in this if statement is to tighten the estimate of
1500 // the divisor. The condition asks if b has any other non-zero limbs.
1501 if (len > 1 && bc_num_nonZeroDig(b->num, len - 1)) {
1503 // This takes a little bit of understanding. The "10*BC_BASE_DIGS/6+1"
1504 // results in either 16 for 64-bit 9-digit limbs or 7 for 32-bit 4-digit
1505 // limbs. Then it shifts a 1 by that many, which in both cases, puts the
1506 // result above *half* of the max value a limb can store. Basically,
1507 // this quickly calculates if the divisor is greater than half the max
1509 nonzero = (divisor > 1 << ((10 * BC_BASE_DIGS) / 6 + 1));
1511 // If the divisor is *not* greater than half the limb...
1514 // Extend the parameters by the number of missing digits in the
1516 bc_num_divExtend(a, b, divisor);
1518 // Check bc_num_d(). In there, we grow a again and again. We do it
1519 // again here; we *always* want to be sure it is big enough.
1520 len = BC_MAX(a->len, b->len);
1521 bc_num_expand(a, len + 1);
1523 // Make a have a zero most significant limb to match the len.
1524 if (len + 1 > a->len) a->len = len + 1;
1526 // Grab the new divisor estimate, new because the shift has made it
1530 divisor = (BcBigDig) b->num[len - 1];
1532 nonzero = bc_num_nonZeroDig(b->num, len - 1);
1536 // If b has other nonzero limbs, we want the divisor to be one higher, so
1537 // that it is an upper bound.
1540 // Make sure c can fit the new length.
1541 bc_num_expand(c, a->len);
1542 memset(c->num, 0, BC_NUM_SIZE(c->cap));
1544 assert(c->scale >= scale);
1545 rdx = BC_NUM_RDX_VAL(c) - BC_NUM_RDX(scale);
1549 bc_num_init(&cpb, len + 1);
1551 BC_SETJMP_LOCKED(err);
1555 // This is the actual division loop.
1556 for (i = end - 1; i < end && i >= rdx && BC_NUM_NONZERO(a); --i) {
1563 assert(n >= a->num);
1566 cmp = bc_num_divCmp(n, b, len);
1568 // This is true if n is greater than b, which means that division can
1569 // proceed, so this inner loop is the part that implements one instance
1573 BcBigDig n1, dividend, quotient;
1575 // These should be named obviously enough. Just imagine that it's a
1576 // division of one limb. Because that's what it is.
1577 n1 = (BcBigDig) n[len];
1578 dividend = n1 * BC_BASE_POW + (BcBigDig) n[len - 1];
1579 quotient = (dividend / divisor);
1581 // If this is true, then we can just subtract. Remember: setting
1582 // quotient to 1 is not bad because we already know that n is
1584 if (quotient <= 1) {
1586 bc_num_subArrays(n, b->num, len);
1590 assert(quotient <= BC_BASE_POW);
1592 // We need to multiply and subtract for a quotient above 1.
1593 bc_num_mulArray(b, (BcBigDig) quotient, &cpb);
1594 bc_num_subArrays(n, cpb.num, cpb.len);
1597 // The result is the *real* quotient, by the way, but it might take
1598 // multiple trips around this loop to get it.
1600 assert(result <= BC_BASE_POW);
1602 // And here's why it might take multiple trips: n might *still* be
1603 // greater than b. So we have to loop again. That's what this is
1604 // setting up for: the condition of the while loop.
1605 if (nonzero) cmp = bc_num_divCmp(n, b, len);
1609 assert(result < BC_BASE_POW);
1611 // Store the actual limb quotient.
1612 c->num[i] = (BcDig) result;
1622 * Implements division. This is a BcNumBinOp function.
1623 * @param a The first operand.
1624 * @param b The second operand.
1625 * @param c The return parameter.
1626 * @param scale The current scale.
1628 static void bc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) {
1633 if (BC_NUM_ZERO(b)) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);
1635 if (BC_NUM_ZERO(a)) {
1636 bc_num_setToZero(c, scale);
1640 if (BC_NUM_ONE(b)) {
1642 bc_num_retireMul(c, scale, BC_NUM_NEG(a), BC_NUM_NEG(b));
1646 // If this is true, we can use bc_num_divArray(), which would be faster.
1647 if (!BC_NUM_RDX_VAL(a) && !BC_NUM_RDX_VAL(b) && b->len == 1 && !scale) {
1649 bc_num_divArray(a, (BcBigDig) b->num[0], c, &rem);
1650 bc_num_retireMul(c, scale, BC_NUM_NEG(a), BC_NUM_NEG(b));
1654 len = bc_num_divReq(a, b, scale);
1658 // Initialize copies of the parameters. We want the length of the first
1659 // operand copy to be as big as the result because of the way the division
1661 bc_num_init(&cpa, len);
1662 bc_num_copy(&cpa, a);
1663 bc_num_createCopy(&cpb, b);
1665 BC_SETJMP_LOCKED(err);
1671 // Like the above comment, we want the copy of the first parameter to be
1672 // larger than the second parameter.
1673 if (len > cpa.len) {
1674 bc_num_expand(&cpa, bc_vm_growSize(len, 2));
1675 bc_num_extend(&cpa, (len - cpa.len) * BC_BASE_DIGS);
1678 cpardx = BC_NUM_RDX_VAL_NP(cpa);
1679 cpa.scale = cpardx * BC_BASE_DIGS;
1681 // This is just setting up the scale in preparation for the division.
1682 bc_num_extend(&cpa, b->scale);
1683 cpardx = BC_NUM_RDX_VAL_NP(cpa) - BC_NUM_RDX(b->scale);
1684 BC_NUM_RDX_SET_NP(cpa, cpardx);
1685 cpa.scale = cpardx * BC_BASE_DIGS;
1687 // Once again, just setting things up, this time to match scale.
1688 if (scale > cpa.scale) {
1689 bc_num_extend(&cpa, scale);
1690 cpardx = BC_NUM_RDX_VAL_NP(cpa);
1691 cpa.scale = cpardx * BC_BASE_DIGS;
1694 // Grow if necessary.
1695 if (cpa.cap == cpa.len) bc_num_expand(&cpa, bc_vm_growSize(cpa.len, 1));
1697 // We want an extra zero in front to make things simpler.
1698 cpa.num[cpa.len++] = 0;
1700 // Still setting things up. Why all of these things are needed is not
1701 // something that can be easily explained, but it has to do with making the
1702 // actual algorithm easier to understand because it can assume a lot of
1703 // things. Thus, you should view all of this setup code as establishing
1704 // assumptions for bc_num_d_long(), where the actual division happens.
1705 if (cpardx == cpa.len) cpa.len = bc_num_nonZeroLen(&cpa);
1706 if (BC_NUM_RDX_VAL_NP(cpb) == cpb.len) cpb.len = bc_num_nonZeroLen(&cpb);
1708 BC_NUM_RDX_SET_NP(cpb, 0);
1710 bc_num_d_long(&cpa, &cpb, c, scale);
1712 bc_num_retireMul(c, scale, BC_NUM_NEG(a), BC_NUM_NEG(b));
1722 * Implements divmod. This is the actual modulus function; since modulus
1723 * requires a division anyway, this returns the quotient and modulus. Either can
1724 * be thrown out as desired.
1725 * @param a The first operand.
1726 * @param b The second operand.
1727 * @param c The return parameter for the quotient.
1728 * @param d The return parameter for the modulus.
1729 * @param scale The current scale.
1730 * @param ts The scale that the operation should be done to. Yes, it's not
1731 * necessarily the same as scale, per the bc spec.
1733 static void bc_num_r(BcNum *a, BcNum *b, BcNum *restrict c,
1734 BcNum *restrict d, size_t scale, size_t ts)
1739 if (BC_NUM_ZERO(b)) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);
1741 if (BC_NUM_ZERO(a)) {
1742 bc_num_setToZero(c, ts);
1743 bc_num_setToZero(d, ts);
1749 bc_num_init(&temp, d->cap);
1751 BC_SETJMP_LOCKED(err);
1756 bc_num_d(a, b, c, scale);
1758 // We want an extra digit so we can safely truncate.
1759 if (scale) scale = ts + 1;
1761 assert(BC_NUM_RDX_VALID(c));
1762 assert(BC_NUM_RDX_VALID(b));
1764 // Implement the rest of the (a - (a / b) * b) formula.
1765 bc_num_m(c, b, &temp, scale);
1766 bc_num_sub(a, &temp, d, scale);
1768 // Extend if necessary.
1769 if (ts > d->scale && BC_NUM_NONZERO(d)) bc_num_extend(d, ts - d->scale);
1771 neg = BC_NUM_NEG(d);
1772 bc_num_retireMul(d, ts, BC_NUM_NEG(a), BC_NUM_NEG(b));
1773 d->rdx = BC_NUM_NEG_VAL(d, BC_NUM_NONZERO(d) ? neg : false);
1782 * Implements modulus/remainder. (Yes, I know they are different, but not in the
1783 * context of bc.) This is a BcNumBinOp function.
1784 * @param a The first operand.
1785 * @param b The second operand.
1786 * @param c The return parameter.
1787 * @param scale The current scale.
1789 static void bc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) {
1794 ts = bc_vm_growSize(scale, b->scale);
1795 ts = BC_MAX(ts, a->scale);
1799 // Need a temp for the quotient.
1800 bc_num_init(&c1, bc_num_mulReq(a, b, ts));
1802 BC_SETJMP_LOCKED(err);
1806 bc_num_r(a, b, &c1, c, scale, ts);
1815 * Implements power (exponentiation). This is a BcNumBinOp function.
1816 * @param a The first operand.
1817 * @param b The second operand.
1818 * @param c The return parameter.
1819 * @param scale The current scale.
1821 static void bc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) {
1825 size_t powrdx, resrdx;
1828 if (BC_ERR(bc_num_nonInt(b, &btemp))) bc_err(BC_ERR_MATH_NON_INTEGER);
1830 if (BC_NUM_ZERO(&btemp)) {
1835 if (BC_NUM_ZERO(a)) {
1836 if (BC_NUM_NEG_NP(btemp)) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);
1837 bc_num_setToZero(c, scale);
1841 if (BC_NUM_ONE(&btemp)) {
1842 if (!BC_NUM_NEG_NP(btemp)) bc_num_copy(c, a);
1843 else bc_num_inv(a, c, scale);
1847 neg = BC_NUM_NEG_NP(btemp);
1848 BC_NUM_NEG_CLR_NP(btemp);
1850 exp = bc_num_bigdig(&btemp);
1854 bc_num_createCopy(©, a);
1856 BC_SETJMP_LOCKED(err);
1860 // If this is true, then we do not have to do a division, and we need to
1861 // set scale accordingly.
1863 size_t max = BC_MAX(scale, a->scale), scalepow;
1864 scalepow = bc_num_mulOverflow(a->scale, exp);
1865 scale = BC_MIN(scalepow, max);
1868 // This is only implementing the first exponentiation by squaring, until it
1869 // reaches the first time where the square is actually used.
1870 for (powrdx = a->scale; !(exp & 1); exp >>= 1) {
1872 assert(BC_NUM_RDX_VALID_NP(copy));
1873 bc_num_mul(©, ©, ©, powrdx);
1876 // Make c a copy of copy for the purpose of saving the squares that should
1878 bc_num_copy(c, ©);
1881 // Now finish the exponentiation by squaring, this time saving the squares
1886 assert(BC_NUM_RDX_VALID_NP(copy));
1887 bc_num_mul(©, ©, ©, powrdx);
1889 // If this is true, we want to save that particular square. This does
1890 // that by multiplying c with copy.
1893 assert(BC_NUM_RDX_VALID(c));
1894 assert(BC_NUM_RDX_VALID_NP(copy));
1895 bc_num_mul(c, ©, c, resrdx);
1899 // Invert if necessary.
1900 if (neg) bc_num_inv(c, c, scale);
1902 // Truncate if necessary.
1903 if (c->scale > scale) bc_num_truncate(c, c->scale - scale);
1913 #if BC_ENABLE_EXTRA_MATH
1915 * Implements the places operator. This is a BcNumBinOp function.
1916 * @param a The first operand.
1917 * @param b The second operand.
1918 * @param c The return parameter.
1919 * @param scale The current scale.
1921 static void bc_num_place(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) {
1927 val = bc_num_intop(a, b, c);
1929 // Just truncate or extend as appropriate.
1930 if (val < c->scale) bc_num_truncate(c, c->scale - val);
1931 else if (val > c->scale) bc_num_extend(c, val - c->scale);
1935 * Implements the left shift operator. This is a BcNumBinOp function.
1937 static void bc_num_left(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) {
1943 val = bc_num_intop(a, b, c);
1945 bc_num_shiftLeft(c, (size_t) val);
1949 * Implements the right shift operator. This is a BcNumBinOp function.
1951 static void bc_num_right(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) {
1957 val = bc_num_intop(a, b, c);
1959 if (BC_NUM_ZERO(c)) return;
1961 bc_num_shiftRight(c, (size_t) val);
1963 #endif // BC_ENABLE_EXTRA_MATH
1966 * Prepares for, and calls, a binary operator function. This is probably the
1967 * most important function in the entire file because it establishes assumptions
1968 * that make the rest of the code so easy. Those assumptions include:
1970 * - a is not the same pointer as c.
1971 * - b is not the same pointer as c.
1972 * - there is enough room in c for the result.
1974 * Without these, this whole function would basically have to be duplicated for
1975 * *all* binary operators.
1977 * @param a The first operand.
1978 * @param b The second operand.
1979 * @param c The return parameter.
1980 * @param scale The current scale.
1981 * @param req The number of limbs needed to fit the result.
1983 static void bc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale,
1984 BcNumBinOp op, size_t req)
1986 BcNum *ptr_a, *ptr_b, num2;
1989 assert(a != NULL && b != NULL && c != NULL && op != NULL);
1991 assert(BC_NUM_RDX_VALID(a));
1992 assert(BC_NUM_RDX_VALID(b));
1996 // Reallocate if c == a.
2001 memcpy(ptr_a, c, sizeof(BcNum));
2008 // Also reallocate if c == b.
2014 memcpy(ptr_b, c, sizeof(BcNum));
2022 // Actually reallocate. If we don't reallocate, we want to expand at the
2026 bc_num_init(c, req);
2028 // Must prepare for cleanup. We want this here so that locals that got
2029 // set stay set since a longjmp() is not guaranteed to preserve locals.
2030 BC_SETJMP_LOCKED(err);
2035 bc_num_expand(c, req);
2038 // It is okay for a and b to be the same. If a binary operator function does
2039 // need them to be different, the binary operator function is responsible
2042 // Call the actual binary operator function.
2043 op(ptr_a, ptr_b, c, scale);
2045 assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
2046 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
2047 assert(BC_NUM_RDX_VALID(c));
2048 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);
2051 // Cleanup only needed if we initialized c to a new number.
2059 #if !defined(NDEBUG) || BC_ENABLE_LIBRARY
2062 * Tests a number string for validity. This function has a history; I originally
2063 * wrote it because I did not trust my parser. Over time, however, I came to
2064 * trust it, so I was able to relegate this function to debug builds only, and I
2065 * used it in assert()'s. But then I created the library, and well, I can't
2066 * trust users, so I reused this for yelling at users.
2067 * @param val The string to check to see if it's a valid number string.
2068 * @return True if the string is a valid number string, false otherwise.
2070 bool bc_num_strValid(const char *restrict val) {
2073 size_t i, len = strlen(val);
2075 // Notice that I don't check if there is a negative sign. That is not part
2076 // of a valid number, except in the library. The library-specific code takes
2077 // care of that part.
2079 // Nothing in the string is okay.
2080 if (!len) return true;
2082 // Loop through the characters.
2083 for (i = 0; i < len; ++i) {
2087 // If we have found a radix point...
2090 // We don't allow two radices.
2091 if (radix) return false;
2097 // We only allow digits and uppercase letters.
2098 if (!(isdigit(c) || isupper(c))) return false;
2103 #endif // !defined(NDEBUG) || BC_ENABLE_LIBRARY
2106 * Parses one character and returns the digit that corresponds to that
2107 * character according to the base.
2108 * @param c The character to parse.
2109 * @param base The base.
2110 * @return The character as a digit.
2112 static BcBigDig bc_num_parseChar(char c, size_t base) {
2114 assert(isupper(c) || isdigit(c));
2119 // This returns the digit that directly corresponds with the letter.
2120 c = BC_NUM_NUM_LETTER(c);
2122 // If the digit is greater than the base, we clamp.
2123 c = ((size_t) c) >= base ? (char) base - 1 : c;
2125 // Straight convert the digit to a number.
2128 return (BcBigDig) (uchar) c;
2132 * Parses a string as a decimal number. This is separate because it's going to
2133 * be the most used, and it can be heavily optimized for decimal only.
2134 * @param n The number to parse into and return. Must be preallocated.
2135 * @param val The string to parse.
2137 static void bc_num_parseDecimal(BcNum *restrict n, const char *restrict val) {
2139 size_t len, i, temp, mod;
2141 bool zero = true, rdx;
2143 // Eat leading zeroes.
2144 for (i = 0; val[i] == '0'; ++i);
2147 assert(!val[0] || isalnum(val[0]) || val[0] == '.');
2149 // All 0's. We can just return, since this procedure expects a virgin
2150 // (already 0) BcNum.
2151 if (!val[0]) return;
2153 // The length of the string is the length of the number, except it might be
2154 // one bigger because of a decimal point.
2157 // Find the location of the decimal point.
2158 ptr = strchr(val, '.');
2159 rdx = (ptr != NULL);
2161 // We eat leading zeroes again. These leading zeroes are different because
2162 // they will come after the decimal point if they exist, and since that's
2163 // the case, they must be preserved.
2164 for (i = 0; i < len && (zero = (val[i] == '0' || val[i] == '.')); ++i);
2166 // Set the scale of the number based on the location of the decimal point.
2167 // The casts to uintptr_t is to ensure that bc does not hit undefined
2168 // behavior when doing math on the values.
2169 n->scale = (size_t) (rdx * (((uintptr_t) (val + len)) -
2170 (((uintptr_t) ptr) + 1)));
2173 BC_NUM_RDX_SET(n, BC_NUM_RDX(n->scale));
2175 // Calculate length. First, the length of the integer, then the number of
2176 // digits in the last limb, then the length.
2177 i = len - (ptr == val ? 0 : i) - rdx;
2178 temp = BC_NUM_ROUND_POW(i);
2179 mod = n->scale % BC_BASE_DIGS;
2180 i = mod ? BC_BASE_DIGS - mod : 0;
2181 n->len = ((temp + i) / BC_BASE_DIGS);
2184 bc_num_expand(n, n->len);
2185 memset(n->num, 0, BC_NUM_SIZE(n->len));
2188 // I think I can set rdx directly to zero here because n should be a
2189 // new number with sign set to false.
2190 n->len = n->rdx = 0;
2194 // There is actually stuff to parse if we make it here. Yay...
2197 assert(i <= BC_NUM_BIGDIG_MAX);
2199 // The exponent and power.
2201 pow = bc_num_pow10[exp];
2203 // Parse loop. We parse backwards because numbers are stored little
2205 for (i = len - 1; i < len; --i, ++exp) {
2209 // Skip the decimal point.
2210 if (c == '.') exp -= 1;
2213 // The index of the limb.
2214 size_t idx = exp / BC_BASE_DIGS;
2216 // Clamp for the base.
2217 if (isupper(c)) c = '9';
2219 // Add the digit to the limb.
2220 n->num[idx] += (((BcBigDig) c) - '0') * pow;
2222 // Adjust the power and exponent.
2223 if ((exp + 1) % BC_BASE_DIGS == 0) pow = 1;
2224 else pow *= BC_BASE;
2231 * Parse a number in any base (besides decimal).
2232 * @param n The number to parse into and return. Must be preallocated.
2233 * @param val The string to parse.
2234 * @param base The base to parse as.
2236 static void bc_num_parseBase(BcNum *restrict n, const char *restrict val,
2239 BcNum temp, mult1, mult2, result1, result2, *m1, *m2, *ptr;
2243 size_t i, digs, len = strlen(val);
2245 // If zero, just return because the number should be virgin (already 0).
2246 for (i = 0; zero && i < len; ++i) zero = (val[i] == '.' || val[i] == '0');
2251 bc_num_init(&temp, BC_NUM_BIGDIG_LOG10);
2252 bc_num_init(&mult1, BC_NUM_BIGDIG_LOG10);
2254 BC_SETJMP_LOCKED(int_err);
2258 // We split parsing into parsing the integer and parsing the fractional
2261 // Parse the integer part. This is the easy part because we just multiply
2262 // the number by the base, then add the digit.
2263 for (i = 0; i < len && (c = val[i]) && c != '.'; ++i) {
2265 // Convert the character to a digit.
2266 v = bc_num_parseChar(c, base);
2268 // Multiply the number.
2269 bc_num_mulArray(n, base, &mult1);
2271 // Convert the digit to a number and add.
2272 bc_num_bigdig2num(&temp, v);
2273 bc_num_add(&mult1, &temp, n, 0);
2276 // If this condition is true, then we are done. We still need to do cleanup
2278 if (i == len && !val[i]) goto int_err;
2280 // If we get here, we *must* be at the radix point.
2281 assert(val[i] == '.');
2285 // Unset the jump to reset in for these new initializations.
2288 bc_num_init(&mult2, BC_NUM_BIGDIG_LOG10);
2289 bc_num_init(&result1, BC_NUM_DEF_SIZE);
2290 bc_num_init(&result2, BC_NUM_DEF_SIZE);
2293 BC_SETJMP_LOCKED(err);
2297 // Pointers for easy switching.
2301 // Parse the fractional part. This is the hard part.
2302 for (i += 1, digs = 0; i < len && (c = val[i]); ++i, ++digs) {
2306 // Convert the character to a digit.
2307 v = bc_num_parseChar(c, base);
2309 // We keep growing result2 according to the base because the more digits
2310 // after the radix, the more significant the digits close to the radix
2312 bc_num_mulArray(&result1, base, &result2);
2314 // Convert the digit to a number.
2315 bc_num_bigdig2num(&temp, v);
2317 // Add the digit into the fraction part.
2318 bc_num_add(&result2, &temp, &result1, 0);
2320 // Keep growing m1 and m2 for use after the loop.
2321 bc_num_mulArray(m1, base, m2);
2323 rdx = BC_NUM_RDX_VAL(m2);
2325 if (m2->len < rdx) m2->len = rdx;
2333 // This one cannot be a divide by 0 because mult starts out at 1, then is
2334 // multiplied by base, and base cannot be 0, so mult cannot be 0. And this
2335 // is the reason we keep growing m1 and m2; this division is what converts
2336 // the parsed fractional part from an integer to a fractional part.
2337 bc_num_div(&result1, m1, &result2, digs * 2);
2340 bc_num_truncate(&result2, digs);
2342 // The final add of the integer part to the fractional part.
2343 bc_num_add(n, &result2, n, digs);
2346 if (BC_NUM_NONZERO(n)) {
2347 if (n->scale < digs) bc_num_extend(n, digs - n->scale);
2349 else bc_num_zero(n);
2353 bc_num_free(&result2);
2354 bc_num_free(&result1);
2355 bc_num_free(&mult2);
2358 bc_num_free(&mult1);
2364 * Prints a backslash+newline combo if the number of characters needs it. This
2365 * is really a convenience function.
2367 static inline void bc_num_printNewline(void) {
2368 #if !BC_ENABLE_LIBRARY
2369 if (vm.nchars >= vm.line_len - 1 && vm.line_len) {
2370 bc_vm_putchar('\\', bc_flush_none);
2371 bc_vm_putchar('\n', bc_flush_err);
2373 #endif // !BC_ENABLE_LIBRARY
2377 * Prints a character after a backslash+newline, if needed.
2378 * @param c The character to print.
2379 * @param bslash Whether to print a backslash+newline.
2381 static void bc_num_putchar(int c, bool bslash) {
2382 if (c != '\n' && bslash) bc_num_printNewline();
2383 bc_vm_putchar(c, bc_flush_save);
2386 #if !BC_ENABLE_LIBRARY
2389 * Prints a character for a number's digit. This is for printing for dc's P
2390 * command. This function does not need to worry about radix points. This is a
2392 * @param n The "digit" to print.
2393 * @param len The "length" of the digit, or number of characters that will
2394 * need to be printed for the digit.
2395 * @param rdx True if a decimal (radix) point should be printed.
2396 * @param bslash True if a backslash+newline should be printed if the character
2397 * limit for the line is reached, false otherwise.
2399 static void bc_num_printChar(size_t n, size_t len, bool rdx, bool bslash) {
2404 bc_vm_putchar((uchar) n, bc_flush_save);
2407 #endif // !BC_ENABLE_LIBRARY
2410 * Prints a series of characters for large bases. This is for printing in bases
2411 * above hexadecimal. This is a BcNumDigitOp.
2412 * @param n The "digit" to print.
2413 * @param len The "length" of the digit, or number of characters that will
2414 * need to be printed for the digit.
2415 * @param rdx True if a decimal (radix) point should be printed.
2416 * @param bslash True if a backslash+newline should be printed if the character
2417 * limit for the line is reached, false otherwise.
2419 static void bc_num_printDigits(size_t n, size_t len, bool rdx, bool bslash) {
2423 // If needed, print the radix; otherwise, print a space to separate digits.
2424 bc_num_putchar(rdx ? '.' : ' ', true);
2426 // Calculate the exponent and power.
2427 for (exp = 0, pow = 1; exp < len - 1; ++exp, pow *= BC_BASE);
2429 // Print each character individually.
2430 for (exp = 0; exp < len; pow /= BC_BASE, ++exp) {
2432 // The individual subdigit.
2433 size_t dig = n / pow;
2435 // Take the subdigit away.
2438 // Print the subdigit.
2439 bc_num_putchar(((uchar) dig) + '0', bslash || exp != len - 1);
2444 * Prints a character for a number's digit. This is for printing in bases for
2445 * hexadecimal and below because they always print only one character at a time.
2446 * This is a BcNumDigitOp.
2447 * @param n The "digit" to print.
2448 * @param len The "length" of the digit, or number of characters that will
2449 * need to be printed for the digit.
2450 * @param rdx True if a decimal (radix) point should be printed.
2451 * @param bslash True if a backslash+newline should be printed if the character
2452 * limit for the line is reached, false otherwise.
2454 static void bc_num_printHex(size_t n, size_t len, bool rdx, bool bslash) {
2461 if (rdx) bc_num_putchar('.', true);
2463 bc_num_putchar(bc_num_hex_digits[n], bslash);
2467 * Prints a decimal number. This is specially written for optimization since
2468 * this will be used the most and because bc's numbers are already in decimal.
2469 * @param n The number to print.
2470 * @param newline Whether to print backslash+newlines on long enough lines.
2472 static void bc_num_printDecimal(const BcNum *restrict n, bool newline) {
2474 size_t i, j, rdx = BC_NUM_RDX_VAL(n);
2476 size_t buffer[BC_BASE_DIGS];
2479 for (i = n->len - 1; i < n->len; --i) {
2481 BcDig n9 = n->num[i];
2483 bool irdx = (i == rdx - 1);
2485 // Calculate the number of digits in the limb.
2486 zero = (zero & !irdx);
2487 temp = n->scale % BC_BASE_DIGS;
2488 temp = i || !temp ? 0 : BC_BASE_DIGS - temp;
2490 memset(buffer, 0, BC_BASE_DIGS * sizeof(size_t));
2492 // Fill the buffer with individual digits.
2493 for (j = 0; n9 && j < BC_BASE_DIGS; ++j) {
2494 buffer[j] = ((size_t) n9) % BC_BASE;
2498 // Print the digits in the buffer.
2499 for (j = BC_BASE_DIGS - 1; j < BC_BASE_DIGS && j >= temp; --j) {
2501 // Figure out whether to print the decimal point.
2502 bool print_rdx = (irdx & (j == BC_BASE_DIGS - 1));
2504 // The zero variable helps us skip leading zero digits in the limb.
2505 zero = (zero && buffer[j] == 0);
2509 // While the first three arguments should be self-explanatory,
2510 // the last needs explaining. I don't want to print a newline
2511 // when the last digit to be printed could take the place of the
2512 // backslash rather than being pushed, as a single character, to
2513 // the next line. That's what that last argument does for bc.
2514 bc_num_printHex(buffer[j], 1, print_rdx,
2515 !newline || (j > temp || i != 0));
2521 #if BC_ENABLE_EXTRA_MATH
2524 * Prints a number in scientific or engineering format. When doing this, we are
2525 * always printing in decimal.
2526 * @param n The number to print.
2527 * @param eng True if we are in engineering mode.
2528 * @param newline Whether to print backslash+newlines on long enough lines.
2530 static void bc_num_printExponent(const BcNum *restrict n,
2531 bool eng, bool newline)
2533 size_t places, mod, nrdx = BC_NUM_RDX_VAL(n);
2534 bool neg = (n->len <= nrdx);
2536 BcDig digs[BC_NUM_BIGDIG_LOG10];
2540 bc_num_createCopy(&temp, n);
2542 BC_SETJMP_LOCKED(exit);
2546 // We need to calculate the exponents, and they change based on whether the
2547 // number is all fractional or not, obviously.
2550 // Figure out how many limbs after the decimal point is zero.
2551 size_t i, idx = bc_num_nonZeroLen(n) - 1;
2555 // Figure out how much in the last limb is zero.
2556 for (i = BC_BASE_DIGS - 1; i < BC_BASE_DIGS; --i) {
2557 if (bc_num_pow10[i] > (BcBigDig) n->num[idx]) places += 1;
2561 // Calculate the combination of zero limbs and zero digits in the last
2563 places += (nrdx - (idx + 1)) * BC_BASE_DIGS;
2566 // Calculate places if we are in engineering mode.
2567 if (eng && mod != 0) places += 3 - mod;
2569 // Shift the temp to the right place.
2570 bc_num_shiftLeft(&temp, places);
2574 // This is the number of digits that we are supposed to put behind the
2576 places = bc_num_intDigits(n) - 1;
2578 // Calculate the true number based on whether engineering mode is
2581 if (eng && mod != 0) places -= 3 - (3 - mod);
2583 // Shift the temp to the right place.
2584 bc_num_shiftRight(&temp, places);
2587 // Print the shifted number.
2588 bc_num_printDecimal(&temp, newline);
2591 bc_num_putchar('e', !newline);
2593 // Need to explicitly print a zero exponent.
2595 bc_num_printHex(0, 1, false, !newline);
2599 // Need to print sign for the exponent.
2600 if (neg) bc_num_putchar('-', true);
2602 // Create a temporary for the exponent...
2603 bc_num_setup(&exp, digs, BC_NUM_BIGDIG_LOG10);
2604 bc_num_bigdig2num(&exp, (BcBigDig) places);
2607 bc_num_printDecimal(&exp, newline);
2614 #endif // BC_ENABLE_EXTRA_MATH
2617 * Converts a number from limbs with base BC_BASE_POW to base @a pow, where
2618 * @a pow is obase^N.
2619 * @param n The number to convert.
2620 * @param rem BC_BASE_POW - @a pow.
2621 * @param pow The power of obase we will convert the number to.
2622 * @param idx The index of the number to start converting at. Doing the
2623 * conversion is O(n^2); we have to sweep through starting at the
2624 * least significant limb
2626 static void bc_num_printFixup(BcNum *restrict n, BcBigDig rem,
2627 BcBigDig pow, size_t idx)
2629 size_t i, len = n->len - idx;
2631 BcDig *a = n->num + idx;
2633 // Ignore if there's just one limb left. This is the part that requires the
2634 // extra loop after the one calling this function in bc_num_printPrepare().
2635 if (len < 2) return;
2637 // Loop through the remaining limbs and convert. We start at the second limb
2638 // because we pull the value from the previous one as well.
2639 for (i = len - 1; i > 0; --i) {
2641 // Get the limb and add it to the previous, along with multiplying by
2642 // the remainder because that's the proper overflow. "acc" means
2643 // "accumulator," by the way.
2644 acc = ((BcBigDig) a[i]) * rem + ((BcBigDig) a[i - 1]);
2646 // Store a value in base pow in the previous limb.
2647 a[i - 1] = (BcDig) (acc % pow);
2649 // Divide by the base and accumulate the remaining value in the limb.
2651 acc += (BcBigDig) a[i];
2653 // If the accumulator is greater than the base...
2654 if (acc >= BC_BASE_POW) {
2656 // Do we need to grow?
2660 len = bc_vm_growSize(len, 1);
2661 bc_num_expand(n, bc_vm_growSize(len, idx));
2663 // Update the pointer because it may have moved.
2666 // Zero out the last limb.
2670 // Overflow into the next limb since we are over the base.
2671 a[i + 1] += acc / BC_BASE_POW;
2675 assert(acc < BC_BASE_POW);
2681 // We may have grown the number, so adjust the length.
2686 * Prepares a number for printing in a base that is not a divisor of
2687 * BC_BASE_POW. This basically converts the number from having limbs of base
2688 * BC_BASE_POW to limbs of pow, where pow is obase^N.
2689 * @param n The number to prepare for printing.
2690 * @param rem The remainder of BC_BASE_POW when divided by a power of the base.
2691 * @param pow The power of the base.
2693 static void bc_num_printPrepare(BcNum *restrict n, BcBigDig rem, BcBigDig pow) {
2697 // Loop from the least significant limb to the most significant limb and
2698 // convert limbs in each pass.
2699 for (i = 0; i < n->len; ++i) bc_num_printFixup(n, rem, pow, i);
2701 // bc_num_printFixup() does not do everything it is supposed to, so we do
2702 // the last bit of cleanup here. That cleanup is to ensure that each limb
2703 // is less than pow and to expand the number to fit new limbs as necessary.
2704 for (i = 0; i < n->len; ++i) {
2706 assert(pow == ((BcBigDig) ((BcDig) pow)));
2708 // If the limb needs fixing...
2709 if (n->num[i] >= (BcDig) pow) {
2711 // Do we need to grow?
2712 if (i + 1 == n->len) {
2715 n->len = bc_vm_growSize(n->len, 1);
2716 bc_num_expand(n, n->len);
2718 // Without this, we might use uninitialized data.
2722 assert(pow < BC_BASE_POW);
2724 // Overflow into the next limb.
2725 n->num[i + 1] += n->num[i] / ((BcDig) pow);
2726 n->num[i] %= (BcDig) pow;
2731 static void bc_num_printNum(BcNum *restrict n, BcBigDig base, size_t len,
2732 BcNumDigitOp print, bool newline)
2735 BcNum intp, fracp1, fracp2, digit, flen1, flen2, *n1, *n2, *temp;
2736 BcBigDig dig = 0, *ptr, acc, exp;
2737 size_t i, j, nrdx, idigits;
2739 BcDig digit_digs[BC_NUM_BIGDIG_LOG10 + 1];
2743 // Easy case. Even with scale, we just print this.
2744 if (BC_NUM_ZERO(n)) {
2745 print(0, len, false, !newline);
2749 // This function uses an algorithm that Stefan Esser <se@freebsd.org> came
2750 // up with to print the integer part of a number. What it does is convert
2751 // intp into a number of the specified base, but it does it directly,
2752 // instead of just doing a series of divisions and printing the remainders
2753 // in reverse order.
2755 // Let me explain in a bit more detail:
2757 // The algorithm takes the current least significant limb (after intp has
2758 // been converted to an integer) and the next to least significant limb, and
2759 // it converts the least significant limb into one of the specified base,
2760 // putting any overflow into the next to least significant limb. It iterates
2761 // through the whole number, from least significant to most significant,
2762 // doing this conversion. At the end of that iteration, the least
2763 // significant limb is converted, but the others are not, so it iterates
2764 // again, starting at the next to least significant limb. It keeps doing
2765 // that conversion, skipping one more limb than the last time, until all
2766 // limbs have been converted. Then it prints them in reverse order.
2768 // That is the gist of the algorithm. It leaves out several things, such as
2769 // the fact that limbs are not always converted into the specified base, but
2770 // into something close, basically a power of the specified base. In
2771 // Stefan's words, "You could consider BcDigs to be of base 10^BC_BASE_DIGS
2772 // in the normal case and obase^N for the largest value of N that satisfies
2773 // obase^N <= 10^BC_BASE_DIGS. [This means that] the result is not in base
2774 // "obase", but in base "obase^N", which happens to be printable as a number
2775 // of base "obase" without consideration for neighbouring BcDigs." This fact
2776 // is what necessitates the existence of the loop later in this function.
2778 // The conversion happens in bc_num_printPrepare() where the outer loop
2779 // happens and bc_num_printFixup() where the inner loop, or actual
2780 // conversion, happens. In other words, bc_num_printPrepare() is where the
2781 // loop that starts at the least significant limb and goes to the most
2782 // significant limb. Then, on every iteration of its loop, it calls
2783 // bc_num_printFixup(), which has the inner loop of actually converting
2784 // the limbs it passes into limbs of base obase^N rather than base
2787 nrdx = BC_NUM_RDX_VAL(n);
2791 // The stack is what allows us to reverse the digits for printing.
2792 bc_vec_init(&stack, sizeof(BcBigDig), BC_DTOR_NONE);
2793 bc_num_init(&fracp1, nrdx);
2795 // intp will be the "integer part" of the number, so copy it.
2796 bc_num_createCopy(&intp, n);
2798 BC_SETJMP_LOCKED(err);
2802 // Make intp an integer.
2803 bc_num_truncate(&intp, intp.scale);
2805 // Get the fractional part out.
2806 bc_num_sub(n, &intp, &fracp1, 0);
2808 // If the base is not the same as the last base used for printing, we need
2809 // to update the cached exponent and power. Yes, we cache the values of the
2810 // exponent and power. That is to prevent us from calculating them every
2811 // time because printing will probably happen multiple times on the same
2813 if (base != vm.last_base) {
2818 // Calculate the exponent and power.
2819 while (vm.last_pow * base <= BC_BASE_POW) {
2820 vm.last_pow *= base;
2824 // Also, the remainder and base itself.
2825 vm.last_rem = BC_BASE_POW - vm.last_pow;
2826 vm.last_base = base;
2831 // If vm.last_rem is 0, then the base we are printing in is a divisor of
2832 // BC_BASE_POW, which is the easy case because it means that BC_BASE_POW is
2833 // a power of obase, and no conversion is needed. If it *is* 0, then we have
2834 // the hard case, and we have to prepare the number for the base.
2835 if (vm.last_rem != 0) bc_num_printPrepare(&intp, vm.last_rem, vm.last_pow);
2837 // After the conversion comes the surprisingly easy part. From here on out,
2838 // this is basically naive code that I wrote, adjusted for the larger bases.
2840 // Fill the stack of digits for the integer part.
2841 for (i = 0; i < intp.len; ++i) {
2844 acc = (BcBigDig) intp.num[i];
2846 // Turn the limb into digits of base obase.
2847 for (j = 0; j < exp && (i < intp.len - 1 || acc != 0); ++j)
2849 // This condition is true if we are not at the last digit.
2861 // Push the digit onto the stack.
2862 bc_vec_push(&stack, &dig);
2868 // Go through the stack backwards and print each digit.
2869 for (i = 0; i < stack.len; ++i) {
2871 ptr = bc_vec_item_rev(&stack, i);
2873 assert(ptr != NULL);
2875 // While the first three arguments should be self-explanatory, the last
2876 // needs explaining. I don't want to print a newline when the last digit
2877 // to be printed could take the place of the backslash rather than being
2878 // pushed, as a single character, to the next line. That's what that
2879 // last argument does for bc.
2880 print(*ptr, len, false, !newline ||
2881 (n->scale != 0 || i == stack.len - 1));
2884 // We are done if there is no fractional part.
2885 if (!n->scale) goto err;
2889 // Reset the jump because some locals are changing.
2892 bc_num_init(&fracp2, nrdx);
2893 bc_num_setup(&digit, digit_digs, sizeof(digit_digs) / sizeof(BcDig));
2894 bc_num_init(&flen1, BC_NUM_BIGDIG_LOG10);
2895 bc_num_init(&flen2, BC_NUM_BIGDIG_LOG10);
2897 BC_SETJMP_LOCKED(frac_err);
2905 // Pointers for easy switching.
2909 fracp2.scale = n->scale;
2910 BC_NUM_RDX_SET_NP(fracp2, BC_NUM_RDX(fracp2.scale));
2912 // As long as we have not reached the scale of the number, keep printing.
2913 while ((idigits = bc_num_intDigits(n1)) <= n->scale) {
2915 // These numbers will keep growing.
2916 bc_num_expand(&fracp2, fracp1.len + 1);
2917 bc_num_mulArray(&fracp1, base, &fracp2);
2919 nrdx = BC_NUM_RDX_VAL_NP(fracp2);
2921 // Ensure an invariant.
2922 if (fracp2.len < nrdx) fracp2.len = nrdx;
2924 // fracp is guaranteed to be non-negative and small enough.
2925 dig = bc_num_bigdig2(&fracp2);
2927 // Convert the digit to a number and subtract it from the number.
2928 bc_num_bigdig2num(&digit, dig);
2929 bc_num_sub(&fracp2, &digit, &fracp1, 0);
2931 // While the first three arguments should be self-explanatory, the last
2932 // needs explaining. I don't want to print a newline when the last digit
2933 // to be printed could take the place of the backslash rather than being
2934 // pushed, as a single character, to the next line. That's what that
2935 // last argument does for bc.
2936 print(dig, len, radix, !newline || idigits != n->scale);
2938 // Update the multipliers.
2939 bc_num_mulArray(n1, base, n2);
2951 bc_num_free(&flen2);
2952 bc_num_free(&flen1);
2953 bc_num_free(&fracp2);
2956 bc_num_free(&fracp1);
2958 bc_vec_free(&stack);
2963 * Prints a number in the specified base, or rather, figures out which function
2964 * to call to print the number in the specified base and calls it.
2965 * @param n The number to print.
2966 * @param base The base to print in.
2967 * @param newline Whether to print backslash+newlines on long enough lines.
2969 static void bc_num_printBase(BcNum *restrict n, BcBigDig base, bool newline) {
2973 bool neg = BC_NUM_NEG(n);
2975 // Clear the sign because it makes the actual printing easier when we have
2979 // Bases at hexadecimal and below are printed as one character, larger bases
2980 // are printed as a series of digits separated by spaces.
2981 if (base <= BC_NUM_MAX_POSIX_IBASE) {
2983 print = bc_num_printHex;
2986 assert(base <= BC_BASE_POW);
2987 width = bc_num_log10(base - 1);
2988 print = bc_num_printDigits;
2992 bc_num_printNum(n, base, width, print, newline);
2995 n->rdx = BC_NUM_NEG_VAL(n, neg);
2998 #if !BC_ENABLE_LIBRARY
3000 void bc_num_stream(BcNum *restrict n) {
3001 bc_num_printNum(n, BC_NUM_STREAM_BASE, 1, bc_num_printChar, false);
3004 #endif // !BC_ENABLE_LIBRARY
3006 void bc_num_setup(BcNum *restrict n, BcDig *restrict num, size_t cap) {
3013 void bc_num_init(BcNum *restrict n, size_t req) {
3017 BC_SIG_ASSERT_LOCKED;
3021 // BC_NUM_DEF_SIZE is set to be about the smallest allocation size that
3022 // malloc() returns in practice, so just use it.
3023 req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
3025 // If we can't use a temp, allocate.
3026 if (req != BC_NUM_DEF_SIZE || (num = bc_vm_takeTemp()) == NULL)
3027 num = bc_vm_malloc(BC_NUM_SIZE(req));
3029 bc_num_setup(n, num, req);
3032 void bc_num_clear(BcNum *restrict n) {
3037 void bc_num_free(void *num) {
3039 BcNum *n = (BcNum*) num;
3041 BC_SIG_ASSERT_LOCKED;
3045 if (n->cap == BC_NUM_DEF_SIZE) bc_vm_addTemp(n->num);
3049 void bc_num_copy(BcNum *d, const BcNum *s) {
3051 assert(d != NULL && s != NULL);
3055 bc_num_expand(d, s->len);
3058 // I can just copy directly here because the sign *and* rdx will be
3059 // properly preserved.
3061 d->scale = s->scale;
3062 memcpy(d->num, s->num, BC_NUM_SIZE(d->len));
3065 void bc_num_createCopy(BcNum *d, const BcNum *s) {
3066 BC_SIG_ASSERT_LOCKED;
3067 bc_num_init(d, s->len);
3071 void bc_num_createFromBigdig(BcNum *restrict n, BcBigDig val) {
3072 BC_SIG_ASSERT_LOCKED;
3073 bc_num_init(n, BC_NUM_BIGDIG_LOG10);
3074 bc_num_bigdig2num(n, val);
3077 size_t bc_num_scale(const BcNum *restrict n) {
3081 size_t bc_num_len(const BcNum *restrict n) {
3083 size_t len = n->len;
3085 // Always return at least 1.
3086 if (BC_NUM_ZERO(n)) return n->scale ? n->scale : 1;
3088 // If this is true, there is no integer portion of the number.
3089 if (BC_NUM_RDX_VAL(n) == len) {
3091 // We have to take into account the fact that some of the digits right
3092 // after the decimal could be zero. If that is the case, we need to
3093 // ignore them until we hit the first non-zero digit.
3097 // The number of limbs with non-zero digits.
3098 len = bc_num_nonZeroLen(n);
3100 // Get the number of digits in the last limb.
3101 scale = n->scale % BC_BASE_DIGS;
3102 scale = scale ? scale : BC_BASE_DIGS;
3104 // Get the number of zero digits.
3105 zero = bc_num_zeroDigits(n->num + len - 1);
3107 // Calculate the true length.
3108 len = len * BC_BASE_DIGS - zero - (BC_BASE_DIGS - scale);
3110 // Otherwise, count the number of int digits and return that plus the scale.
3111 else len = bc_num_intDigits(n) + n->scale;
3116 void bc_num_parse(BcNum *restrict n, const char *restrict val, BcBigDig base) {
3118 assert(n != NULL && val != NULL && base);
3119 assert(base >= BC_NUM_MIN_BASE && base <= vm.maxes[BC_PROG_GLOBALS_IBASE]);
3120 assert(bc_num_strValid(val));
3122 // A one character number is *always* parsed as though the base was the
3123 // maximum allowed ibase, per the bc spec.
3125 BcBigDig dig = bc_num_parseChar(val[0], BC_NUM_MAX_LBASE);
3126 bc_num_bigdig2num(n, dig);
3128 else if (base == BC_BASE) bc_num_parseDecimal(n, val);
3129 else bc_num_parseBase(n, val, base);
3131 assert(BC_NUM_RDX_VALID(n));
3134 void bc_num_print(BcNum *restrict n, BcBigDig base, bool newline) {
3137 assert(BC_ENABLE_EXTRA_MATH || base >= BC_NUM_MIN_BASE);
3139 // We may need a newline, just to start.
3140 bc_num_printNewline();
3142 if (BC_NUM_NONZERO(n)) {
3145 if (BC_NUM_NEG(n)) bc_num_putchar('-', true);
3147 // Print the leading zero if necessary.
3148 if (BC_Z && BC_NUM_RDX_VAL(n) == n->len)
3149 bc_num_printHex(0, 1, false, !newline);
3153 if (BC_NUM_ZERO(n)) bc_num_printHex(0, 1, false, !newline);
3154 else if (base == BC_BASE) bc_num_printDecimal(n, newline);
3155 #if BC_ENABLE_EXTRA_MATH
3156 else if (base == 0 || base == 1)
3157 bc_num_printExponent(n, base != 0, newline);
3158 #endif // BC_ENABLE_EXTRA_MATH
3159 else bc_num_printBase(n, base, newline);
3161 if (newline) bc_num_putchar('\n', false);
3164 BcBigDig bc_num_bigdig2(const BcNum *restrict n) {
3166 // This function returns no errors because it's guaranteed to succeed if
3167 // its preconditions are met. Those preconditions include both n needs to
3168 // be non-NULL, n being non-negative, and n being less than vm.max. If all
3169 // of that is true, then we can just convert without worrying about negative
3170 // errors or overflow.
3173 size_t nrdx = BC_NUM_RDX_VAL(n);
3176 assert(!BC_NUM_NEG(n));
3177 assert(bc_num_cmp(n, &vm.max) < 0);
3178 assert(n->len - nrdx <= 3);
3180 // There is a small speed win from unrolling the loop here, and since it
3181 // only adds 53 bytes, I decided that it was worth it.
3182 switch (n->len - nrdx) {
3186 r = (BcBigDig) n->num[nrdx + 2];
3193 r = r * BC_BASE_POW + (BcBigDig) n->num[nrdx + 1];
3200 r = r * BC_BASE_POW + (BcBigDig) n->num[nrdx];
3207 BcBigDig bc_num_bigdig(const BcNum *restrict n) {
3211 // This error checking is extremely important, and if you do not have a
3212 // guarantee that converting a number will always succeed in a particular
3213 // case, you *must* call this function to get these error checks. This
3214 // includes all instances of numbers inputted by the user or calculated by
3215 // the user. Otherwise, you can call the faster bc_num_bigdig2().
3216 if (BC_ERR(BC_NUM_NEG(n))) bc_err(BC_ERR_MATH_NEGATIVE);
3217 if (BC_ERR(bc_num_cmp(n, &vm.max) >= 0)) bc_err(BC_ERR_MATH_OVERFLOW);
3219 return bc_num_bigdig2(n);
3222 void bc_num_bigdig2num(BcNum *restrict n, BcBigDig val) {
3234 // Expand first. This is the only way this function can fail, and it's a
3236 bc_num_expand(n, BC_NUM_BIGDIG_LOG10);
3238 // The conversion is easy because numbers are laid out in little-endian
3240 for (ptr = n->num, i = 0; val; ++i, val /= BC_BASE_POW)
3241 ptr[i] = val % BC_BASE_POW;
3246 #if BC_ENABLE_EXTRA_MATH
3248 void bc_num_rng(const BcNum *restrict n, BcRNG *rng) {
3250 BcNum temp, temp2, intn, frac;
3251 BcRand state1, state2, inc1, inc2;
3252 size_t nrdx = BC_NUM_RDX_VAL(n);
3254 // This function holds the secret of how I interpret a seed number for the
3255 // PRNG. Well, it's actually in the development manual
3256 // (manuals/development.md#pseudo-random-number-generator), so look there
3257 // before you try to understand this.
3261 bc_num_init(&temp, n->len);
3262 bc_num_init(&temp2, n->len);
3263 bc_num_init(&frac, nrdx);
3264 bc_num_init(&intn, bc_num_int(n));
3266 BC_SETJMP_LOCKED(err);
3270 assert(BC_NUM_RDX_VALID_NP(vm.max));
3272 memcpy(frac.num, n->num, BC_NUM_SIZE(nrdx));
3274 BC_NUM_RDX_SET_NP(frac, nrdx);
3275 frac.scale = n->scale;
3277 assert(BC_NUM_RDX_VALID_NP(frac));
3278 assert(BC_NUM_RDX_VALID_NP(vm.max2));
3280 // Multiply the fraction and truncate so that it's an integer. The
3281 // truncation is what clamps it, by the way.
3282 bc_num_mul(&frac, &vm.max2, &temp, 0);
3283 bc_num_truncate(&temp, temp.scale);
3284 bc_num_copy(&frac, &temp);
3287 memcpy(intn.num, n->num + nrdx, BC_NUM_SIZE(bc_num_int(n)));
3288 intn.len = bc_num_int(n);
3290 // This assert is here because it has to be true. It is also here to justify
3291 // some optimizations.
3292 assert(BC_NUM_NONZERO(&vm.max));
3294 // If there *was* a fractional part...
3295 if (BC_NUM_NONZERO(&frac)) {
3297 // This divmod splits frac into the two state parts.
3298 bc_num_divmod(&frac, &vm.max, &temp, &temp2, 0);
3300 // frac is guaranteed to be smaller than vm.max * vm.max (pow).
3301 // This means that when dividing frac by vm.max, as above, the
3302 // quotient and remainder are both guaranteed to be less than vm.max,
3303 // which means we can use bc_num_bigdig2() here and not worry about
3305 state1 = (BcRand) bc_num_bigdig2(&temp2);
3306 state2 = (BcRand) bc_num_bigdig2(&temp);
3308 else state1 = state2 = 0;
3310 // If there *was* an integer part...
3311 if (BC_NUM_NONZERO(&intn)) {
3313 // This divmod splits intn into the two inc parts.
3314 bc_num_divmod(&intn, &vm.max, &temp, &temp2, 0);
3316 // Because temp2 is the mod of vm.max, from above, it is guaranteed
3317 // to be small enough to use bc_num_bigdig2().
3318 inc1 = (BcRand) bc_num_bigdig2(&temp2);
3320 // Clamp the second inc part.
3321 if (bc_num_cmp(&temp, &vm.max) >= 0) {
3322 bc_num_copy(&temp2, &temp);
3323 bc_num_mod(&temp2, &vm.max, &temp, 0);
3326 // The if statement above ensures that temp is less than vm.max, which
3327 // means that we can use bc_num_bigdig2() here.
3328 inc2 = (BcRand) bc_num_bigdig2(&temp);
3330 else inc1 = inc2 = 0;
3332 bc_rand_seed(rng, state1, state2, inc1, inc2);
3338 bc_num_free(&temp2);
3343 void bc_num_createFromRNG(BcNum *restrict n, BcRNG *rng) {
3345 BcRand s1, s2, i1, i2;
3346 BcNum conv, temp1, temp2, temp3;
3347 BcDig temp1_num[BC_RAND_NUM_SIZE], temp2_num[BC_RAND_NUM_SIZE];
3348 BcDig conv_num[BC_NUM_BIGDIG_LOG10];
3352 bc_num_init(&temp3, 2 * BC_RAND_NUM_SIZE);
3354 BC_SETJMP_LOCKED(err);
3358 bc_num_setup(&temp1, temp1_num, sizeof(temp1_num) / sizeof(BcDig));
3359 bc_num_setup(&temp2, temp2_num, sizeof(temp2_num) / sizeof(BcDig));
3360 bc_num_setup(&conv, conv_num, sizeof(conv_num) / sizeof(BcDig));
3362 // This assert is here because it has to be true. It is also here to justify
3363 // the assumption that vm.max is not zero.
3364 assert(BC_NUM_NONZERO(&vm.max));
3366 // Because this is true, we can just ignore math errors that would happen
3368 assert(BC_NUM_NONZERO(&vm.max2));
3370 bc_rand_getRands(rng, &s1, &s2, &i1, &i2);
3372 // Put the second piece of state into a number.
3373 bc_num_bigdig2num(&conv, (BcBigDig) s2);
3375 assert(BC_NUM_RDX_VALID_NP(conv));
3377 // Multiply by max to make room for the first piece of state.
3378 bc_num_mul(&conv, &vm.max, &temp1, 0);
3380 // Add in the first piece of state.
3381 bc_num_bigdig2num(&conv, (BcBigDig) s1);
3382 bc_num_add(&conv, &temp1, &temp2, 0);
3384 // Divide to make it an entirely fractional part.
3385 bc_num_div(&temp2, &vm.max2, &temp3, BC_RAND_STATE_BITS);
3387 // Now start on the increment parts. It's the same process without the
3388 // divide, so put the second piece of increment into a number.
3389 bc_num_bigdig2num(&conv, (BcBigDig) i2);
3391 assert(BC_NUM_RDX_VALID_NP(conv));
3393 // Multiply by max to make room for the first piece of increment.
3394 bc_num_mul(&conv, &vm.max, &temp1, 0);
3396 // Add in the first piece of increment.
3397 bc_num_bigdig2num(&conv, (BcBigDig) i1);
3398 bc_num_add(&conv, &temp1, &temp2, 0);
3400 // Now add the two together.
3401 bc_num_add(&temp2, &temp3, n, 0);
3403 assert(BC_NUM_RDX_VALID(n));
3407 bc_num_free(&temp3);
3411 void bc_num_irand(BcNum *restrict a, BcNum *restrict b, BcRNG *restrict rng) {
3418 if (BC_ERR(BC_NUM_NEG(a))) bc_err(BC_ERR_MATH_NEGATIVE);
3420 // If either of these are true, then the numbers are integers.
3421 if (BC_NUM_ZERO(a) || BC_NUM_ONE(a)) return;
3423 if (BC_ERR(bc_num_nonInt(a, &atemp))) bc_err(BC_ERR_MATH_NON_INTEGER);
3427 len = atemp.len - 1;
3429 // Just generate a random number for each limb.
3430 for (i = 0; i < len; ++i)
3431 b->num[i] = (BcDig) bc_rand_bounded(rng, BC_BASE_POW);
3433 // Do the last digit explicitly because the bound must be right. But only
3434 // do it if the limb does not equal 1. If it does, we have already hit the
3436 if (atemp.num[i] != 1) {
3437 b->num[i] = (BcDig) bc_rand_bounded(rng, (BcRand) atemp.num[i]);
3440 // We want 1 less len in the case where we skip the last limb.
3445 assert(BC_NUM_RDX_VALID(b));
3447 #endif // BC_ENABLE_EXTRA_MATH
3449 size_t bc_num_addReq(const BcNum *a, const BcNum *b, size_t scale) {
3451 size_t aint, bint, ardx, brdx;
3453 // Addition and subtraction require the max of the length of the two numbers
3458 ardx = BC_NUM_RDX_VAL(a);
3459 aint = bc_num_int(a);
3460 assert(aint <= a->len && ardx <= a->len);
3462 brdx = BC_NUM_RDX_VAL(b);
3463 bint = bc_num_int(b);
3464 assert(bint <= b->len && brdx <= b->len);
3466 ardx = BC_MAX(ardx, brdx);
3467 aint = BC_MAX(aint, bint);
3469 return bc_vm_growSize(bc_vm_growSize(ardx, aint), 1);
3472 size_t bc_num_mulReq(const BcNum *a, const BcNum *b, size_t scale) {
3476 // Multiplication requires the sum of the lengths of the numbers.
3478 rdx = bc_vm_growSize(BC_NUM_RDX_VAL(a), BC_NUM_RDX_VAL(b));
3480 max = BC_NUM_RDX(scale);
3482 max = bc_vm_growSize(BC_MAX(max, rdx), 1);
3483 rdx = bc_vm_growSize(bc_vm_growSize(bc_num_int(a), bc_num_int(b)), max);
3488 size_t bc_num_divReq(const BcNum *a, const BcNum *b, size_t scale) {
3492 // Division requires the length of the dividend plus the scale.
3494 rdx = bc_vm_growSize(BC_NUM_RDX_VAL(a), BC_NUM_RDX_VAL(b));
3496 max = BC_NUM_RDX(scale);
3498 max = bc_vm_growSize(BC_MAX(max, rdx), 1);
3499 rdx = bc_vm_growSize(bc_num_int(a), max);
3504 size_t bc_num_powReq(const BcNum *a, const BcNum *b, size_t scale) {
3506 return bc_vm_growSize(bc_vm_growSize(a->len, b->len), 1);
3509 #if BC_ENABLE_EXTRA_MATH
3510 size_t bc_num_placesReq(const BcNum *a, const BcNum *b, size_t scale) {
3512 return a->len + b->len - BC_NUM_RDX_VAL(a) - BC_NUM_RDX_VAL(b);
3514 #endif // BC_ENABLE_EXTRA_MATH
3516 void bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3517 assert(BC_NUM_RDX_VALID(a));
3518 assert(BC_NUM_RDX_VALID(b));
3519 bc_num_binary(a, b, c, false, bc_num_as, bc_num_addReq(a, b, scale));
3522 void bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3523 assert(BC_NUM_RDX_VALID(a));
3524 assert(BC_NUM_RDX_VALID(b));
3525 bc_num_binary(a, b, c, true, bc_num_as, bc_num_addReq(a, b, scale));
3528 void bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3529 assert(BC_NUM_RDX_VALID(a));
3530 assert(BC_NUM_RDX_VALID(b));
3531 bc_num_binary(a, b, c, scale, bc_num_m, bc_num_mulReq(a, b, scale));
3534 void bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3535 assert(BC_NUM_RDX_VALID(a));
3536 assert(BC_NUM_RDX_VALID(b));
3537 bc_num_binary(a, b, c, scale, bc_num_d, bc_num_divReq(a, b, scale));
3540 void bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3541 assert(BC_NUM_RDX_VALID(a));
3542 assert(BC_NUM_RDX_VALID(b));
3543 bc_num_binary(a, b, c, scale, bc_num_rem, bc_num_divReq(a, b, scale));
3546 void bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3547 assert(BC_NUM_RDX_VALID(a));
3548 assert(BC_NUM_RDX_VALID(b));
3549 bc_num_binary(a, b, c, scale, bc_num_p, bc_num_powReq(a, b, scale));
3552 #if BC_ENABLE_EXTRA_MATH
3553 void bc_num_places(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3554 assert(BC_NUM_RDX_VALID(a));
3555 assert(BC_NUM_RDX_VALID(b));
3556 bc_num_binary(a, b, c, scale, bc_num_place, bc_num_placesReq(a, b, scale));
3559 void bc_num_lshift(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3560 assert(BC_NUM_RDX_VALID(a));
3561 assert(BC_NUM_RDX_VALID(b));
3562 bc_num_binary(a, b, c, scale, bc_num_left, bc_num_placesReq(a, b, scale));
3565 void bc_num_rshift(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
3566 assert(BC_NUM_RDX_VALID(a));
3567 assert(BC_NUM_RDX_VALID(b));
3568 bc_num_binary(a, b, c, scale, bc_num_right, bc_num_placesReq(a, b, scale));
3570 #endif // BC_ENABLE_EXTRA_MATH
3572 void bc_num_sqrt(BcNum *restrict a, BcNum *restrict b, size_t scale) {
3574 BcNum num1, num2, half, f, fprime, *x0, *x1, *temp;
3575 size_t pow, len, rdx, req, resscale;
3578 assert(a != NULL && b != NULL && a != b);
3580 if (BC_ERR(BC_NUM_NEG(a))) bc_err(BC_ERR_MATH_NEGATIVE);
3582 // We want to calculate to a's scale if it is bigger so that the result will
3583 // truncate properly.
3584 if (a->scale > scale) scale = a->scale;
3586 // Set parameters for the result.
3587 len = bc_vm_growSize(bc_num_intDigits(a), 1);
3588 rdx = BC_NUM_RDX(scale);
3590 // Square root needs half of the length of the parameter.
3591 req = bc_vm_growSize(BC_MAX(rdx, BC_NUM_RDX_VAL(a)), len >> 1);
3595 // Unlike the binary operators, this function is the only single parameter
3596 // function and is expected to initialize the result. This means that it
3597 // expects that b is *NOT* preallocated. We allocate it here.
3598 bc_num_init(b, bc_vm_growSize(req, 1));
3602 assert(a != NULL && b != NULL && a != b);
3603 assert(a->num != NULL && b->num != NULL);
3606 if (BC_NUM_ZERO(a)) {
3607 bc_num_setToZero(b, scale);
3611 // Another easy case.
3612 if (BC_NUM_ONE(a)) {
3614 bc_num_extend(b, scale);
3618 // Set the parameters again.
3619 rdx = BC_NUM_RDX(scale);
3620 rdx = BC_MAX(rdx, BC_NUM_RDX_VAL(a));
3621 len = bc_vm_growSize(a->len, rdx);
3625 bc_num_init(&num1, len);
3626 bc_num_init(&num2, len);
3627 bc_num_setup(&half, half_digs, sizeof(half_digs) / sizeof(BcDig));
3629 // There is a division by two in the formula. We setup a number that's 1/2
3630 // so that we can use multiplication instead of heavy division.
3632 half.num[0] = BC_BASE_POW / 2;
3634 BC_NUM_RDX_SET_NP(half, 1);
3637 bc_num_init(&f, len);
3638 bc_num_init(&fprime, len);
3640 BC_SETJMP_LOCKED(err);
3644 // Pointers for easy switching.
3651 // The power of the operand is needed for the estimate.
3652 pow = bc_num_intDigits(a);
3654 // The code in this if statement calculates the initial estimate. First, if
3655 // a is less than 0, then 0 is a good estimate. Otherwise, we want something
3656 // in the same ballpark. That ballpark is pow.
3659 // An odd number is served by starting with 2^((pow-1)/2), and an even
3660 // number is served by starting with 6^((pow-2)/2). Why? Because math.
3661 if (pow & 1) x0->num[0] = 2;
3662 else x0->num[0] = 6;
3664 pow -= 2 - (pow & 1);
3665 bc_num_shiftLeft(x0, pow / 2);
3668 // I can set the rdx here directly because neg should be false.
3669 x0->scale = x0->rdx = 0;
3670 resscale = (scale + BC_BASE_DIGS) + 2;
3672 // This is the calculation loop. This compare goes to 0 eventually as the
3673 // difference between the two numbers gets smaller than resscale.
3674 while (bc_num_cmp(x1, x0)) {
3676 assert(BC_NUM_NONZERO(x0));
3678 // This loop directly corresponds to the iteration in Newton's method.
3679 // If you know the formula, this loop makes sense. Go study the formula.
3681 bc_num_div(a, x0, &f, resscale);
3682 bc_num_add(x0, &f, &fprime, resscale);
3684 assert(BC_NUM_RDX_VALID_NP(fprime));
3685 assert(BC_NUM_RDX_VALID_NP(half));
3687 bc_num_mul(&fprime, &half, x1, resscale);
3695 // Copy to the result and truncate.
3697 if (b->scale > scale) bc_num_truncate(b, b->scale - scale);
3699 assert(!BC_NUM_NEG(b) || BC_NUM_NONZERO(b));
3700 assert(BC_NUM_RDX_VALID(b));
3701 assert(BC_NUM_RDX_VAL(b) <= b->len || !b->len);
3702 assert(!b->len || b->num[b->len - 1] || BC_NUM_RDX_VAL(b) == b->len);
3706 bc_num_free(&fprime);
3713 void bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale) {
3719 // The bulk of this function is just doing what bc_num_binary() does for the
3720 // binary operators. However, it assumes that only c and a can be equal.
3722 // Set up the parameters.
3723 ts = BC_MAX(scale + b->scale, a->scale);
3724 len = bc_num_mulReq(a, b, ts);
3726 assert(a != NULL && b != NULL && c != NULL && d != NULL);
3727 assert(c != d && a != d && b != d && b != c);
3729 // Initialize or expand as necessary.
3732 memcpy(&num2, c, sizeof(BcNum));
3737 bc_num_init(c, len);
3741 BC_SETJMP_LOCKED(err);
3747 bc_num_expand(c, len);
3750 // Do the quick version if possible.
3751 if (BC_NUM_NONZERO(a) && !BC_NUM_RDX_VAL(a) &&
3752 !BC_NUM_RDX_VAL(b) && b->len == 1 && !scale)
3756 bc_num_divArray(ptr_a, (BcBigDig) b->num[0], c, &rem);
3758 assert(rem < BC_BASE_POW);
3760 d->num[0] = (BcDig) rem;
3761 d->len = (rem != 0);
3763 // Do the slow method.
3764 else bc_num_r(ptr_a, b, c, d, scale, ts);
3766 assert(!BC_NUM_NEG(c) || BC_NUM_NONZERO(c));
3767 assert(BC_NUM_RDX_VALID(c));
3768 assert(BC_NUM_RDX_VAL(c) <= c->len || !c->len);
3769 assert(!c->len || c->num[c->len - 1] || BC_NUM_RDX_VAL(c) == c->len);
3770 assert(!BC_NUM_NEG(d) || BC_NUM_NONZERO(d));
3771 assert(BC_NUM_RDX_VALID(d));
3772 assert(BC_NUM_RDX_VAL(d) <= d->len || !d->len);
3773 assert(!d->len || d->num[d->len - 1] || BC_NUM_RDX_VAL(d) == d->len);
3776 // Only cleanup if we initialized.
3784 void bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d) {
3786 BcNum base, exp, two, temp, atemp, btemp, ctemp;
3789 assert(a != NULL && b != NULL && c != NULL && d != NULL);
3790 assert(a != d && b != d && c != d);
3792 if (BC_ERR(BC_NUM_ZERO(c))) bc_err(BC_ERR_MATH_DIVIDE_BY_ZERO);
3794 if (BC_ERR(BC_NUM_NEG(b))) bc_err(BC_ERR_MATH_NEGATIVE);
3797 // This is entirely for quieting a useless scan-build error.
3802 // Eliminate fractional parts that are zero or error if they are not zero.
3803 if (BC_ERR(bc_num_nonInt(a, &atemp) || bc_num_nonInt(b, &btemp) ||
3804 bc_num_nonInt(c, &ctemp)))
3806 bc_err(BC_ERR_MATH_NON_INTEGER);
3809 bc_num_expand(d, ctemp.len);
3813 bc_num_init(&base, ctemp.len);
3814 bc_num_setup(&two, two_digs, sizeof(two_digs) / sizeof(BcDig));
3815 bc_num_init(&temp, btemp.len + 1);
3816 bc_num_createCopy(&exp, &btemp);
3818 BC_SETJMP_LOCKED(err);
3826 // We already checked for 0.
3827 bc_num_rem(&atemp, &ctemp, &base, 0);
3829 // If you know the algorithm I used, the memory-efficient method, then this
3830 // loop should be self-explanatory because it is the calculation loop.
3831 while (BC_NUM_NONZERO(&exp)) {
3833 // Num two cannot be 0, so no errors.
3834 bc_num_divmod(&exp, &two, &exp, &temp, 0);
3836 if (BC_NUM_ONE(&temp) && !BC_NUM_NEG_NP(temp)) {
3838 assert(BC_NUM_RDX_VALID(d));
3839 assert(BC_NUM_RDX_VALID_NP(base));
3841 bc_num_mul(d, &base, &temp, 0);
3843 // We already checked for 0.
3844 bc_num_rem(&temp, &ctemp, d, 0);
3847 assert(BC_NUM_RDX_VALID_NP(base));
3849 bc_num_mul(&base, &base, &temp, 0);
3851 // We already checked for 0.
3852 bc_num_rem(&temp, &ctemp, &base, 0);
3861 assert(!BC_NUM_NEG(d) || d->len);
3862 assert(BC_NUM_RDX_VALID(d));
3863 assert(!d->len || d->num[d->len - 1] || BC_NUM_RDX_VAL(d) == d->len);
3867 void bc_num_printDebug(const BcNum *n, const char *name, bool emptyline) {
3868 bc_file_puts(&vm.fout, bc_flush_none, name);
3869 bc_file_puts(&vm.fout, bc_flush_none, ": ");
3870 bc_num_printDecimal(n, true);
3871 bc_file_putchar(&vm.fout, bc_flush_err, '\n');
3872 if (emptyline) bc_file_putchar(&vm.fout, bc_flush_err, '\n');
3876 void bc_num_printDigs(const BcDig *n, size_t len, bool emptyline) {
3880 for (i = len - 1; i < len; --i)
3881 bc_file_printf(&vm.fout, " %lu", (unsigned long) n[i]);
3883 bc_file_putchar(&vm.fout, bc_flush_err, '\n');
3884 if (emptyline) bc_file_putchar(&vm.fout, bc_flush_err, '\n');
3888 void bc_num_printWithDigs(const BcNum *n, const char *name, bool emptyline) {
3889 bc_file_puts(&vm.fout, bc_flush_none, name);
3890 bc_file_printf(&vm.fout, " len: %zu, rdx: %zu, scale: %zu\n",
3891 name, n->len, BC_NUM_RDX_VAL(n), n->scale);
3892 bc_num_printDigs(n->num, n->len, emptyline);
3895 void bc_num_dump(const char *varname, const BcNum *n) {
3897 ulong i, scale = n->scale;
3899 bc_file_printf(&vm.ferr, "\n%s = %s", varname,
3900 n->len ? (BC_NUM_NEG(n) ? "-" : "+") : "0 ");
3902 for (i = n->len - 1; i < n->len; --i) {
3904 if (i + 1 == BC_NUM_RDX_VAL(n))
3905 bc_file_puts(&vm.ferr, bc_flush_none, ". ");
3907 if (scale / BC_BASE_DIGS != BC_NUM_RDX_VAL(n) - i - 1)
3908 bc_file_printf(&vm.ferr, "%lu ", (unsigned long) n->num[i]);
3911 int mod = scale % BC_BASE_DIGS;
3912 int d = BC_BASE_DIGS - mod;
3916 div = n->num[i] / ((BcDig) bc_num_pow10[(ulong) d]);
3917 bc_file_printf(&vm.ferr, "%lu", (unsigned long) div);
3920 div = n->num[i] % ((BcDig) bc_num_pow10[(ulong) d]);
3921 bc_file_printf(&vm.ferr, " ' %lu ", (unsigned long) div);
3925 bc_file_printf(&vm.ferr, "(%zu | %zu.%zu / %zu) %lu\n",
3926 n->scale, n->len, BC_NUM_RDX_VAL(n), n->cap,
3927 (unsigned long) (void*) n->num);
3929 bc_file_flush(&vm.ferr, bc_flush_err);
3931 #endif // BC_DEBUG_CODE