Re: [boost] Re: big_int, was Re: New file uploaded to boost

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-07-04 15:56:07

Helmut Zeisel wrote:

> Anyway, I think that the discussion is focusing too much on the implementation,
> not on the interface.

        I don't agree. The interface is determined by the
types chosen. If you use a word size WORD, then it is natural to
provide a fast version of:

        big_int * WORD -> big_int

> If you did not like my interface, however, it would be worse.

        The basic interface is trivially obvious.
You need the basic operations:

        add, subtract, multiply, quotient_and_remainder
        comparisons

and probably some mutators. The hard part is what _other_
operations to provide. In particular, conversions to
and from WHICH other types? What about a specialised
multiply and divide by 10? What about n_digits?
Log2?

        If you look at a serious big int library,
you'll find all sorts of weird functions. They're
there because

        a) they provide very fast computations for
           special cases

        b) they're needed for something non-obvious

for example, you really MUST have n_digits, so you can
estimate how big a char array to allocate to fit
the string representation of the number in.

You also must have 'multiply by 10 and add digit',
because that is the way in which you'd build a number
from a string of digits.

Multiply by 10 can be very fast (10 = 8 + 2,
so it can be done with shifts and an add).

My point is that it isn't possible to discover what you
really need in an interface with an implementation that 
isn't trying to provide the fastest possible way to calculate.

Here's the big int interface from the Ocaml big_int module,
note that at the time this was written, Ocaml only had one
size of integer (int).

type big_int

val sign_big_int : big_int -> int
val zero_big_int : big_int
val unit_big_int : big_int
val num_digits_big_int : big_int -> int
val minus_big_int : big_int -> big_int
val abs_big_int : big_int -> big_int
val compare_big_int : big_int -> big_int -> int
val eq_big_int : big_int -> big_int -> bool
val le_big_int : big_int -> big_int -> bool
val ge_big_int : big_int -> big_int -> bool
val lt_big_int : big_int -> big_int -> bool
val gt_big_int : big_int -> big_int -> bool
val max_big_int : big_int -> big_int -> big_int
val min_big_int : big_int -> big_int -> big_int
val pred_big_int : big_int -> big_int
val succ_big_int : big_int -> big_int
val add_big_int : big_int -> big_int -> big_int
val big_int_of_int : int -> big_int
val add_int_big_int : int -> big_int -> big_int
val sub_big_int : big_int -> big_int -> big_int
val mult_int_big_int : int -> big_int -> big_int
val mult_big_int : big_int -> big_int -> big_int
val quomod_big_int : big_int -> big_int -> big_int * big_int
val div_big_int : big_int -> big_int -> big_int
val mod_big_int : big_int -> big_int -> big_int
val gcd_big_int : big_int -> big_int -> big_int
val int_of_big_int : big_int -> int
val is_int_big_int : big_int -> bool
val nat_of_big_int : big_int -> nat
val big_int_of_nat : nat -> big_int
val string_of_big_int : big_int -> string
val big_int_of_string : string -> big_int
val float_of_big_int : big_int -> float
val square_big_int: big_int -> big_int
val sqrt_big_int: big_int -> big_int
val base_power_big_int: int -> int -> big_int -> big_int
val sys_big_int_of_string: string -> int -> int -> big_int
val power_int_positive_int: int -> int -> big_int
val power_big_int_positive_int: big_int -> int -> big_int
val power_int_positive_big_int: int -> big_int -> big_int
val power_big_int_positive_big_int: big_int -> big_int -> big_int
val round_futur_last_digit : string -> int -> int -> bool
val approx_big_int: int -> big_int -> string

and here's the one for unsigned numbers:

type nat

(* Natural numbers (type [nat]) are positive integers of arbitrary size.
   All operations on [nat] are performed in-place. *)

external create_nat: int -> nat = "create_nat"
val make_nat: int -> nat
external set_to_zero_nat: nat -> int -> int -> unit = "set_to_zero_nat"
external blit_nat: nat -> int -> nat -> int -> int -> unit = "blit_nat"
val copy_nat: nat -> int -> int -> nat
external set_digit_nat: nat -> int -> int -> unit = "set_digit_nat"
external nth_digit_nat: nat -> int -> int = "nth_digit_nat"
val length_nat: nat -> int
val length_nat : nat -> int 
external num_digits_nat: nat -> int -> int -> int = "num_digits_nat"
external num_leading_zero_bits_in_digit: nat -> int -> int =
"num_leading_zero_bits_in_digit"
external is_digit_int: nat -> int -> bool = "is_digit_int"
external is_digit_zero: nat -> int -> bool = "is_digit_zero"
external is_digit_normalized: nat -> int -> bool = "is_digit_normalized"
external is_digit_odd: nat -> int -> bool = "is_digit_odd"
val is_zero_nat: nat -> int -> int -> bool
val is_nat_int: nat -> int -> int -> bool
val int_of_nat: nat -> int
val nat_of_int: int -> nat
external incr_nat: nat -> int -> int -> int -> int = "incr_nat"
external add_nat: nat -> int -> int -> nat -> int -> int -> int -> int =
"add_nat" "add_nat_native"
external complement_nat: nat -> int -> int -> unit = "complement_nat"
external decr_nat: nat -> int -> int -> int -> int = "decr_nat"
external sub_nat: nat -> int -> int -> nat -> int -> int -> int -> int =
"sub_nat" "sub_nat_native"
external mult_digit_nat: nat -> int -> int -> nat -> int -> int -> nat
-> int -> int = "mult_digit_nat" "mult_digit_nat_native"
external mult_nat: nat -> int -> int -> nat -> int -> int -> nat -> int
-> int -> int = "mult_nat" "mult_nat_native"
external shift_left_nat: nat -> int -> int -> nat -> int -> int -> unit
= "shift_left_nat" "shift_left_nat_native"
external div_digit_nat: nat -> int -> nat -> int -> nat -> int -> int ->
nat -> int -> unit = "div_digit_nat" "div_digit_nat_native"
external div_nat: nat -> int -> int -> nat -> int -> int -> unit =
"div_nat" "div_nat_native"
external shift_right_nat: nat -> int -> int -> nat -> int -> int -> unit
= "shift_right_nat" "shift_right_nat_native"
external compare_digits_nat: nat -> int -> nat -> int -> int =
"compare_digits_nat"
external compare_nat: nat -> int -> int -> nat -> int -> int -> int =
"compare_nat" "compare_nat_native"
val eq_nat : nat -> int -> int -> nat -> int -> int -> bool
val le_nat : nat -> int -> int -> nat -> int -> int -> bool
val lt_nat : nat -> int -> int -> nat -> int -> int -> bool
val ge_nat : nat -> int -> int -> nat -> int -> int -> bool
val gt_nat : nat -> int -> int -> nat -> int -> int -> bool
external land_digit_nat: nat -> int -> nat -> int -> unit =
"land_digit_nat"
external lor_digit_nat: nat -> int -> nat -> int -> unit =
"lor_digit_nat"
external lxor_digit_nat: nat -> int -> nat -> int -> unit =
"lxor_digit_nat"
val square_nat : nat -> int -> int -> nat -> int -> int -> int
val gcd_nat : nat -> int -> int -> nat -> int -> int -> int
val sqrt_nat : nat -> int -> int -> nat
val string_of_nat : nat -> string
val nat_of_string : string -> nat
val sys_nat_of_string : int -> string -> int -> int -> nat
val float_of_nat : nat -> float
val make_power_base :  int -> nat -> int * int
val power_base_int : int -> int -> nat
val length_of_digit: int

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net