summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>2007-10-13 04:37:18 (GMT)
committerH. Peter Anvin <hpa@zytor.com>2007-10-13 04:37:18 (GMT)
commitf997d209424b0a8a2ee865a2d459fc574f8316c0 (patch)
treebf486100f35835c661555a6072018d5391e1a223
parentf3dab4e3133387571752d14e7508b6341ed7b464 (diff)
downloadpbn-f997d209424b0a8a2ee865a2d459fc574f8316c0.zip
pbn-f997d209424b0a8a2ee865a2d459fc574f8316c0.tar.gz
pbn-f997d209424b0a8a2ee865a2d459fc574f8316c0.tar.bz2
pbn-f997d209424b0a8a2ee865a2d459fc574f8316c0.tar.xz
Add a routine for "small division" (bignum/smallnum)
Small division can be done much more efficiently than big division, so make small division available to the user.
-rw-r--r--Makefile2
-rw-r--r--pbn.h3
-rw-r--r--pbn_divs.c72
-rw-r--r--test.c21
4 files changed, 97 insertions, 1 deletions
diff --git a/Makefile b/Makefile
index b97cd90..3124843 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,7 @@ LDFLAGS =
LIBOBJ = pbn_add.o pbn_cmp.o pbn_dump.o pbn_init.o pbn_mul.o pbn_shift.o \
pbn_and.o pbn_or.o pbn_xor.o pbn_bit.o \
- pbn_abs.o pbn_div.o
+ pbn_abs.o pbn_div.o pbn_divs.o
TESTS = test
diff --git a/pbn.h b/pbn.h
index 42b0959..28cf763 100644
--- a/pbn.h
+++ b/pbn.h
@@ -28,6 +28,8 @@
#define PBN_ATOM_BITS 32
#define PBN_ATOM_xFMT "08"PRIx32
+#define PBN_ATOM_dFMT "08"PRId32
+#define PBN_ATOM_uFMT "08"PRIu32
typedef uint32_t pbn_atom_t;
typedef uint64_t pbn_2atom_t;
typedef int32_t pbn_satom_t;
@@ -64,6 +66,7 @@ int pbn_cmp(const struct pbn *, const struct pbn *);
int pbn_abscmp(const struct pbn *, const struct pbn *);
struct pbn *pbn_mul(struct pbn *, struct pbn *);
int pbn_div(struct pbn **, struct pbn **, struct pbn *, struct pbn *);
+int pbn_divs(struct pbn **, pbn_satom_t *, struct pbn *, pbn_satom_t);
struct pbn *pbn_abs(struct pbn *);
struct pbn *pbn_shr(struct pbn *, int);
diff --git a/pbn_divs.c b/pbn_divs.c
new file mode 100644
index 0000000..e88e3a6
--- /dev/null
+++ b/pbn_divs.c
@@ -0,0 +1,72 @@
+/* ----------------------------------------------------------------------- *
+ *
+ * Copyright 2007 H. Peter Anvin - All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation, Inc.,
+ * 59 Temple Place Ste 330, Boston MA 02111-1307, USA; version 2.1,
+ * incorporated herein by reference.
+ *
+ * ----------------------------------------------------------------------- */
+
+/*
+ * pbn_divs.c
+ *
+ * "Small division"
+ *
+ * Divide a large number with a small (single-atom) number
+ */
+
+#include "pbnint.h"
+
+int pbn_divs(struct pbn **qp, pbn_satom_t *rp, struct pbn *n, pbn_satom_t d)
+{
+ int i;
+ int len;
+ struct pbn *q;
+ pbn_2atom_t c;
+ int minus;
+
+ if (d == 0) {
+ if (rp)
+ *rp = 0;
+ if (qp)
+ *qp = n;
+ else
+ pbn_free(n);
+
+ return -1; /* Division by zero */
+ }
+
+ len = (n->bits+PBN_ATOM_BITS-1)/PBN_ATOM_BITS;
+ q = pbn_new(len);
+
+ minus = n->minus ^ (d < 0);
+ if (d < 0)
+ d = -d;
+
+ q->minus = minus;
+
+ c = 0;
+ for (i = len-1; i >= 0; i--) {
+ c = (c << PBN_ATOM_BITS) + n->num[i];
+
+ /* N.B. the explicit casts allow some compilers to tell this is
+ a 2A:A -> A division operation. */
+ q->num[i] = (pbn_atom_t)(c/d);
+ c = (pbn_atom_t)(c%d);
+ }
+
+ pbn_free(n);
+
+ if (rp)
+ *rp = minus ? -(pbn_satom_t)c : (pbn_satom_t)c;
+
+ if (qp)
+ *qp = pbn_adjust_bits(q);
+ else
+ pbn_free(q);
+
+ return 0;
+}
diff --git a/test.c b/test.c
index 17bd788..1ae09cb 100644
--- a/test.c
+++ b/test.c
@@ -59,6 +59,26 @@ static void divide_test(void)
putchar('\n');
}
+static void small_divide_test(void)
+{
+ struct pbn *n, *q;
+ pbn_satom_t r;
+ int rv;
+
+ printf("\n*** Small divide test ***\n\n");
+
+ /* 2^128/3 */
+
+ n = pbn_new(5);
+ n->num[4] = 1; /* 2^128 */
+ pbn_adjust_bits(n);
+
+ rv = pbn_divs(&q, &r, n, 3);
+
+ pbn_dump(stdout, q);
+ printf(" : %"PBN_ATOM_xFMT"\n", r);
+}
+
int main(int argc, char *argv[])
{
uint64_t i, j;
@@ -139,6 +159,7 @@ int main(int argc, char *argv[])
pbn_free(m);
divide_test();
+ small_divide_test();
return 0;
}