From: Richard Jones <rich@an...>  20050425 09:47:36

On Mon, Apr 25, 2005 at 03:53:31PM +0900, Janne Hellsten wrote: > If there's any concern about the speed of 'big_int_of_int', perhaps it > could be optimized by having big_int representations of range > 128..128 stored in an array and looking these up in case the input > parameter falls into this range. If the input parameter is out of > this range, then the generic 'big_int_of_int' would be used. Yes, you're right. To be honest I was getting very frustrated trying to write a MillerRabin implementation for ExtBig_int, and was thinking about moving to Numerix, which is probably what I should have used in the first place. Only problem is that the GODI distribution on my laptop is having upgrade problems ... I'll release what I have at some point and we can discuss whether it's worth adding to extlib or not. Rich.  Richard Jones, CTO Merjis Ltd. Merjis  web marketing and technology  http://merjis.com Team Notepad  intranets and extranets for business  http://teamnotepad.com 
From: Richard Jones <rich@an...>  20050424 22:53:57

A suggestion for ExtBig_int interface below. I'm about 3/4 way through the implementation, which will follow. Comments welcome. Some comments of my own: * Big_int is implemented on top of Nat. I got halfway through the implementation before realising this, but it looks like I might have tackled this at the wrong level. OTOH, Big_int itself provides no way to access the underlying Nat; also I suspect that most people will be using Big_int directly, even for number theoretical / crypto work, because Nat (natural numbers) can be too limiting. * Some of the functions overlap with work done by Numerix / Cryptokit / GMP. My intention wasn't to make this be a competitor to these  just to make Big_ints a bit more useful out of the box. * I added lsl, lsr, land, lor and lxor operators. These are useful but unfortunately the implementation is very slow because the basic Big_int module doesn't really provide any bitoriented methods. We could get around this by using Obj.magic to break encapsulation, but the implementation would then be both complex and fragile. * My current implementation of Big_int <> binary representations is slow, also because of the previous point. * Factorization would be nice, but I'm not confident that I can implement a suitable algorithm. Perhaps this area is just too specialised for extlib. Rich.  (* * ExtBig_int  Additional functions for handling big_ints. * Copyright (C) 2005 Richard W.M. Jones * * This library 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; either * version 2.1 of the License, or (at your option) any later version, * with the special exception on linking described in file LICENSE. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 021111307 USA *) (** Additional functions for handing [big_int]s. *) module Big_int : sig type big_int (** The type of big integers. *) (** {6 New Functions} *) val one_big_int : big_int val two_big_int : big_int val three_big_int : big_int val four_big_int : big_int val five_big_int : big_int val six_big_int : big_int val seven_big_int : big_int val eight_big_int : big_int val nine_big_int : big_int val ten_big_int : big_int val sixteen_big_int : big_int val twenty_big_int : big_int val thirty_big_int : big_int val thirty_two_big_int : big_int val fourty_big_int : big_int val fifty_big_int : big_int val sixty_big_int : big_int val sixty_four_big_int : big_int val seventy_big_int : big_int val eighty_big_int : big_int val ninety_big_int : big_int val hundred_big_int : big_int val minus_one_big_int : big_int val minus_two_big_int : big_int val minus_three_big_int : big_int val minus_four_big_int : big_int val minus_five_big_int : big_int val minus_six_big_int : big_int val minus_seven_big_int : big_int val minus_eight_big_int : big_int val minus_nine_big_int : big_int val minus_ten_big_int : big_int val minus_sixteen_big_int : big_int val minus_twenty_big_int : big_int val minus_thirty_big_int : big_int val minus_thirty_two_big_int : big_int val minus_fourty_big_int : big_int val minus_fifty_big_int : big_int val minus_sixty_big_int : big_int val minus_sixty_four_big_int : big_int val minus_seventy_big_int : big_int val minus_eighty_big_int : big_int val minus_ninety_big_int : big_int val minus_hundred_big_int : big_int (** The constant big integers [1], [2], [3], ..., [1], [2], [3], ... . *) val is_zero_big_int : big_int > bool val is_one_big_int : big_int > bool val is_minus_one_big_int : big_int > bool (** These functions return true iff the [big_int] parameter is equal to [0] / [1] / [1]. *) val compare_int_big_int : int > big_int > int (** [compare_int_big_int i bi] compares [int] [i] to [big_int] [bi], returning [0] if [i] and [bi] are numerically equal, or [1] if [i] is greater than [bi], or [1] if [i] is less than [bi]. *) val is_odd_big_int : big_int > bool val is_even_big_int : big_int > bool (** These functions return true iff the [big_int] parameter is odd / even. *) val lsl_big_int : big_int > int > big_int (** Logical shift left the [big_int] by a number of [bits]. The result is undefined if [bits < 0]. The sign bit is ignored for the purposes of shifting. *) val lsr_big_int : big_int > int > big_int (** Logical shift right the [big_int] by a number of [bits]. The result is undefined if [bits < 0]. The sign bit is ignored for the purposes of shifting. *) val land_big_int : big_int > big_int > big_int (** Logical bitwise AND of two [big_int]s. The sign bit is ignored. *) val lor_big_int : big_int > big_int > big_int (** Logical bitwise OR of two [big_int]s. The sign bit is ignored. *) val lxor_big_int : big_int > big_int > big_int (** Logical bitwise XOR of two [big_int]s. The sign bit is ignored. *) val double_big_int : big_int > big_int (** [double_big_int n] is equivalent to [lsl_big_int n 1]. *) val half_big_int : big_int > big_int (** [half_big_int n] is equivalent to [lsr_big_int n 1]. *) val add_two_big_int : big_int > big_int val sub_two_big_int : big_int > big_int (** Add / subtract [2] from the [big_int]. *) val power_of_two_big_int : int > big_int (** [power_of_two_big_int n] returns [2^n] as a [big_int]. *) val binary_of_big_int : big_int > int list (** [binary_of_big_int n] returns [n] as a list of [0]s and [1]s, representing the shortest binary representation of [n]. The most significant bit is the head of the list. *) val big_int_of_binary : int list > big_int (** [big_int_of_binary bits]. [bits] should be a list of [0]s and [1]s only. The function returns the big_int of the binary representation from the list. The most significant bit should be first in the list. *) val binary_string_of_big_int : big_int > string (** [binary_string_of_big_int] returns [n] as a string containing only ['0'] and ['1'] characters, representing the shortest binary representation of [n]. The most significant bit is the first character of the string. *) val big_int_of_binary_string : string > big_int (** [big_int_of_binary_string bits]. [bits] should be a list of ['0'] and ['1'] characters only. The function returns the big_int of the binary representation in the string. The most significant bit should be first character of the string. *) val random_big_int : ?f:(unit > int * int) > int > big_int (** [random_big_int bits] returns a random big_int of length [bits] bits. The result will be between [0] and [2^bits  1]. If the optional [~f] parameter is not passed, then the standard OCaml random number generator is used (ie. the function {!Random.bits}). To gain more control over the source of randomness  for instance to supply random numbers from an external source of entropy  the caller should supply a function [~f] of type [unit > int * int]. For each call this function should return [(random, bits)]. The first element of the tuple should be a positive random integer. The second element of the tuple should be the number of bits of randomness contained in the random integer, where [1 <= bits <= 30]. [random_big_int] may raise [Failure] if [~f] returns a negative random integer, or if [bits] is outside the proscribed range. *) val random_prime_big_int : ?f:(unit > int * int) > ?prime_test:(big_int > bool) > int > big_int (** [random_prime_big_int bits] returns a random prime in the range [0] to [2^bits  1]. [bits >= 1] else this function will raise [Invalid_argument]. The optional function parameter [~f] can be used to pass in an external source of entropy, as is described in {!random_big_int}. The optional function parameter [~prime_test] can be used to pass in a primality testing function. By default the function {!is_prime_bit_int} is used. *) val miller_rabin_primality_big_int : big_int > rounds:int > bool (** Probabilistic primality test for big int using the MillerRabin method. [~rounds] is the number of rounds of testing to perform. The confidence that the number is actually prime if this function returns [true] is [1  1 / 4^rounds]. *) val is_prime_big_int : big_int > bool (** Probabilistic test of primality using a suitable algorithm with reasonable defaults. *) (* val factorize_big_int : big_int > (big_int * int) list (** Factorize the [big_int] into factors using a suitable algorithm. Returns a list of the unique factors and the multiplicity of each. For example, [factorize_big_int (big_int_of_int 100)] would return the list [[ big_int_of_int 2, 2; big_int_of_int 5, 2 ]], meaning that [100 = 2^2 * 5^2]. Note that factorizing large numbers can be slow. *) *) (** {6 Older Functions} *) (** Please refer to the OCaml Manual for documentation for these functions. *) val zero_big_int : big_int val unit_big_int : big_int val minus_big_int : big_int > big_int val abs_big_int : big_int > big_int val add_big_int : big_int > big_int > big_int val succ_big_int : big_int > big_int val add_int_big_int : int > big_int > big_int val sub_big_int : big_int > big_int > big_int val pred_big_int : big_int > big_int val mult_big_int : big_int > big_int > big_int val mult_int_big_int : int > big_int > big_int val square_big_int: big_int > big_int val sqrt_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 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 sign_big_int : big_int > 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 num_digits_big_int : big_int > int val string_of_big_int : big_int > string val big_int_of_string : string > big_int val big_int_of_int : int > big_int val is_int_big_int : big_int > bool val int_of_big_int : big_int > int val float_of_big_int : big_int > float (** {6 For internal use} *) val nat_of_big_int : big_int > Nat.nat val big_int_of_nat : Nat.nat > 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 round_futur_last_digit : string > int > int > bool val approx_big_int: int > big_int > string end  Richard Jones, CTO Merjis Ltd. Merjis  web marketing and technology  http://merjis.com Team Notepad  intranets and extranets for business  http://teamnotepad.com 
From: Janne Hellsten <jjhellst@gm...>  20050425 02:27:38

Hi, > val one_big_int : big_int > val two_big_int : big_int ... > val hundred_big_int : big_int Is there some reason (other than optimization) for not using big_int_of_int instead? Best regards, Janne 
From: Richard Jones <rich@an...>  20050425 02:51:14

On Mon, Apr 25, 2005 at 11:27:29AM +0900, Janne Hellsten wrote: > Hi, > > > val one_big_int : big_int > > val two_big_int : big_int > ... > > val hundred_big_int : big_int > > Is there some reason (other than optimization) for not using > big_int_of_int instead? Not really sure to be honest. In the code I was originally writing I kept on having to define constants I was using at the top level  to avoid having to frequently write '(big_int_of_int 2)' all over the place. Whether it makes a real difference or not I don't know. Rich.  Richard Jones, CTO Merjis Ltd. Merjis  web marketing and technology  http://merjis.com Team Notepad  intranets and extranets for business  http://teamnotepad.com 
From: Janne Hellsten <jjhellst@gm...>  20050425 06:53:38

> Not really sure to be honest. >=20 > In the code I was originally writing I kept on having to define > constants I was using at the top level  to avoid having to frequently > write '(big_int_of_int 2)' all over the place. Whether it makes a > real difference or not I don't know. The reason I was asking, is that the majority of the API consists of these constants and IMHO brings some redundancy into the API. By removing these constants we would also nullify the need to argue about which constants in the range 100..100 are the most precious to developers ;) If there's any concern about the speed of 'big_int_of_int', perhaps it could be optimized by having big_int representations of range 128..128 stored in an array and looking these up in case the input parameter falls into this range. If the input parameter is out of this range, then the generic 'big_int_of_int' would be used. Best regards, Janne 
From: Richard Jones <rich@an...>  20050425 09:47:36

On Mon, Apr 25, 2005 at 03:53:31PM +0900, Janne Hellsten wrote: > If there's any concern about the speed of 'big_int_of_int', perhaps it > could be optimized by having big_int representations of range > 128..128 stored in an array and looking these up in case the input > parameter falls into this range. If the input parameter is out of > this range, then the generic 'big_int_of_int' would be used. Yes, you're right. To be honest I was getting very frustrated trying to write a MillerRabin implementation for ExtBig_int, and was thinking about moving to Numerix, which is probably what I should have used in the first place. Only problem is that the GODI distribution on my laptop is having upgrade problems ... I'll release what I have at some point and we can discuss whether it's worth adding to extlib or not. Rich.  Richard Jones, CTO Merjis Ltd. Merjis  web marketing and technology  http://merjis.com Team Notepad  intranets and extranets for business  http://teamnotepad.com 
From: Nicolas Cannasse <warplayer@fr...>  20050425 09:57:46

> > If there's any concern about the speed of 'big_int_of_int', perhaps it > > could be optimized by having big_int representations of range > > 128..128 stored in an array and looking these up in case the input > > parameter falls into this range. If the input parameter is out of > > this range, then the generic 'big_int_of_int' would be used. > > Yes, you're right. To be honest I was getting very frustrated trying > to write a MillerRabin implementation for ExtBig_int, and was > thinking about moving to Numerix, which is probably what I should have > used in the first place. Only problem is that the GODI distribution > on my laptop is having upgrade problems ... > > I'll release what I have at some point and we can discuss whether it's > worth adding to extlib or not. > > Rich. I personaly never had the use for Bigints, so I might not the best to decide whatever extensions are needed or not. Does some other people here already felt frustrated with current Bigint API ? Nicolas 
From: William D. Neumann <wneumann@cs...>  20050425 15:58:23

On Mon, 25 Apr 2005, Nicolas Cannasse wrote: > I personaly never had the use for Bigints, so I might not the best to decide > whatever extensions are needed or not. Does some other people here already > felt frustrated with current Bigint API ? Well, I rarely use it due to it's excessive verbosity (which could be helped by a separate Infixes module, a la mlgmp) as well as its lack of bitwise operations and features like to/from_string_base, where you can input/output big ints in formats other than decimal. However, I'm more concerned with the fact that it's... well... broken <http://pauillac.inria.fr/bin/camlbugs/open?id=3586>;. William D. Neumann  "There's just so many extra children, we could just feed the children to these tigers. We don't need them, we're not doing anything with them. Tigers are noble and sleek; children are loud and messy."  Neko Case Think of XML as Lisp for COBOL programmers.  TonyA (some guy on /.) 