summaryrefslogtreecommitdiff
path: root/lib/bigint.ml
diff options
context:
space:
mode:
authorGravatar Stephane Glondu <steph@glondu.net>2010-07-21 09:46:51 +0200
committerGravatar Stephane Glondu <steph@glondu.net>2010-07-21 09:46:51 +0200
commit5b7eafd0f00a16d78f99a27f5c7d5a0de77dc7e6 (patch)
tree631ad791a7685edafeb1fb2e8faeedc8379318ae /lib/bigint.ml
parentda178a880e3ace820b41d38b191d3785b82991f5 (diff)
Imported Upstream snapshot 8.3~beta0+13298
Diffstat (limited to 'lib/bigint.ml')
-rw-r--r--lib/bigint.ml32
1 files changed, 14 insertions, 18 deletions
diff --git a/lib/bigint.ml b/lib/bigint.ml
index 7671b0fc..f505bbe1 100644
--- a/lib/bigint.ml
+++ b/lib/bigint.ml
@@ -6,7 +6,7 @@
(* * GNU Lesser General Public License Version 2.1 *)
(************************************************************************)
-(* $Id: bigint.ml 9821 2007-05-11 17:00:58Z aspiwack $ *)
+(* $Id$ *)
(*i*)
open Pp
@@ -19,8 +19,8 @@ open Pp
(* An integer is canonically represented as an array of k-digits blocs.
0 is represented by the empty array and -1 by the singleton [|-1|].
- The first bloc is in the range ]0;10^k[ for positive numbers.
- The first bloc is in the range ]-10^k;-1[ for negative ones.
+ The first bloc is in the range ]0;10^k[ for positive numbers.
+ The first bloc is in the range ]-10^k;-1[ for negative ones.
All other blocs are numbers in the range [0;10^k[.
Negative numbers are represented using 2's complementation. For instance,
@@ -78,7 +78,7 @@ let normalize_neg n =
if Array.length n' = 0 then [|-1|] else (n'.(0) <- n'.(0) - base; n')
let rec normalize n =
- if Array.length n = 0 then n else
+ if Array.length n = 0 then n else
if n.(0) = -1 then normalize_neg n else normalize_pos n
let neg m =
@@ -167,8 +167,6 @@ let less_than m n =
(Array.length m = Array.length n && less_than_same_size m n 0 0))
let equal m n = (m = n)
-
-let less_or_equal_than m n = equal m n or less_than m n
let less_than_shift_pos k m n =
(Array.length m - k < Array.length n)
@@ -194,7 +192,7 @@ let euclid m d =
if is_strictly_neg m then (-1),neg m else 1,Array.copy m in
let isnegd, d = if is_strictly_neg d then (-1),neg d else 1,d in
if d = zero then raise Division_by_zero;
- let q,r =
+ let q,r =
if less_than m d then (zero,m) else
let ql = Array.length m - Array.length d in
let q = Array.create (ql+1) 0 in
@@ -202,7 +200,7 @@ let euclid m d =
while not (less_than_shift_pos !i m d) do
if m.(!i)=0 then incr i else
if can_divide !i m d 0 then begin
- let v =
+ let v =
if Array.length d > 1 && d.(0) <> m.(!i) then
(m.(!i) * base + m.(!i+1)) / (d.(0) * base + d.(1) + 1)
else
@@ -234,11 +232,11 @@ let of_string s =
let r = (String.length s - !d) mod size in
let h = String.sub s (!d) r in
if !d = String.length s - 1 && isneg && h="1" then neg_one else
- let e = if h<>"" then 1 else 0 in
+ let e = if h<>"" then 1 else 0 in
let l = (String.length s - !d) / size in
let a = Array.create (l + e + n) 0 in
if isneg then begin
- a.(0) <- (-1);
+ a.(0) <- (-1);
let carry = ref 0 in
for i=l downto 1 do
let v = int_of_string (String.sub s ((i-1)*size + !d +r) size)+ !carry in
@@ -298,7 +296,7 @@ let app_pair f (m, n) =
(f m, f n)
let add m n =
- if Obj.is_int m & Obj.is_int n
+ if Obj.is_int m & Obj.is_int n
then big_of_int (coerce_to_int m + coerce_to_int n)
else big_of_ints (add (ints_of_z m) (ints_of_z n))
@@ -313,8 +311,8 @@ let mult m n =
else big_of_ints (mult (ints_of_z m) (ints_of_z n))
let euclid m n =
- if Obj.is_int m & Obj.is_int n
- then app_pair big_of_int
+ if Obj.is_int m & Obj.is_int n
+ then app_pair big_of_int
(coerce_to_int m / coerce_to_int n, coerce_to_int m mod coerce_to_int n)
else app_pair big_of_ints (euclid (ints_of_z m) (ints_of_z n))
@@ -335,9 +333,7 @@ let one = big_of_int 1
let sub_1 n = sub n one
let add_1 n = add n one
let two = big_of_int 2
-let neg_two = big_of_int (-2)
let mult_2 n = add n n
-let is_zero n = n=zero
let div2_with_rest n =
let (q,b) = euclid n two in
@@ -364,12 +360,12 @@ let pow =
let (quo,rem) = div2_with_rest m in
pow_aux
((* [if m mod 2 = 1]*)
- if rem then
+ if rem then
mult n odd_rest
else
odd_rest )
(* quo = [m/2] *)
- (mult n n) quo
+ (mult n n) quo
in
pow_aux one
@@ -397,7 +393,7 @@ let check () =
let s = Printf.sprintf "%30s" (to_string n) in
let s' = Printf.sprintf "% 30.0f" (round n') in
if s <> s' then Printf.printf "%s: %s <> %s\n" op s s' in
-List.iter (fun a -> List.iter (fun b ->
+List.iter (fun a -> List.iter (fun b ->
let n = of_string a and m = of_string b in
let n' = float_of_string a and m' = float_of_string b in
let a = add n m and a' = n' +. m' in