monotone

monotone Mtn Source Tree

Root/botan/divide.cpp

1/*************************************************
2* Division Algorithm Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/numthry.h>
7#include <botan/mp_core.h>
8
9namespace Botan {
10
11/*************************************************
12* Solve x = q * y + r *
13*************************************************/
14void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
15 {
16 BigInt y = y_arg;
17 r = x;
18
19 r.set_sign(BigInt::Positive);
20 y.set_sign(BigInt::Positive);
21
22 modifying_divide(r, y, q);
23
24 if(x.sign() == BigInt::Negative)
25 {
26 q.flip_sign();
27 if(r.is_nonzero()) { --q; r = y_arg.abs() - r; }
28 }
29 if(y_arg.sign() == BigInt::Negative)
30 q.flip_sign();
31 }
32
33/*************************************************
34* Solve x = q * y + r *
35*************************************************/
36void positive_divide(const BigInt& x, const BigInt& y_arg,
37 BigInt& q, BigInt& r)
38 {
39 BigInt y = y_arg;
40 r = x;
41 modifying_divide(r, y, q);
42 }
43
44/*************************************************
45* Solve x = q * y + r *
46*************************************************/
47void modifying_divide(BigInt& x, BigInt& y, BigInt& q)
48 {
49 if(y.is_zero())
50 throw BigInt::DivideByZero();
51 if(x.is_negative() || y.is_negative())
52 throw Invalid_Argument("Arguments to modifying_divide must be positive");
53
54 s32bit compare = x.cmp(y);
55 if(compare == -1) { q = 0; return; }
56 if(compare == 0) { q = 1; x = 0; return; }
57
58 u32bit shifts = 0;
59 while(y[y.sig_words()-1] < MP_WORD_TOP_BIT)
60 { x <<= 1; y <<= 1; shifts++; }
61
62 u32bit n = x.sig_words() - 1, t = y.sig_words() - 1;
63 q.reg.create(n - t + 1);
64 if(n <= t)
65 {
66 while(x > y) { x -= y; q.add(1); }
67 x >>= shifts;
68 return;
69 }
70
71 BigInt temp = y << (MP_WORD_BITS * (n-t));
72
73 while(x >= temp) { x -= temp; q[n-t]++; }
74
75 for(u32bit j = n; j != t; j--)
76 {
77 const word x_j0 = x.word_at(j);
78 const word x_j1 = x.word_at(j-1);
79 const word y_t = y.word_at(t);
80
81 if(x_j0 == y_t)
82 q[j-t-1] = MP_WORD_MAX;
83 else
84 q[j-t-1] = bigint_divop(x_j0, x_j1, y_t);
85
86 while(bigint_divcore(q[j-t-1], y_t, y.word_at(t-1),
87 x_j0, x_j1, x.word_at(j-2)))
88 q[j-t-1]--;
89
90 x -= (q[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
91 if(x.is_negative())
92 {
93 x += y << (MP_WORD_BITS * (j-t-1));
94 q[j-t-1]--;
95 }
96 }
97 x >>= shifts;
98 }
99
100}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status