[ccan] Mathematics Module

Rusty Russell rusty at rustcorp.com.au
Wed Feb 4 01:21:54 EST 2009


On Sunday 01 February 2009 00:40:02 Rupinder Singh wrote:
> Hello,
> 
> Here are the improvements/corrections:
> 
> 1) is_prime2 : Calculation of prime numbers using Sieve of Eratosthenes. Can
> be used to determine whether a number is prime (by uncommenting certain
> statements) , but is_prime should be used for that due to its superior
> efficiency.

Hi Rupinder,

   I think your original code was in fact optimal.  For example, it takes
about 7.1 seconds to figure out that 36028797018963971 is prime on my
64 bit machine here.

> 2) is_square : O(1) routine to establish if a number is a perfect square

   Interesting use of sqrt().  This needs linking against the math library
on most systems, which makes for an interesting CCAN problem (how do we
specify this?).  But on modern machines with a sqrt instruction, it's
probably optimal.

> 3) gcd : example string corrected (Uses Euclid's Algorithm)
> 
> Apart from these very basic routines, there are 5-6 numerical methods that I
> wish to add. I wanted to know If there could be a bit of STL ? Or strictly C
> ?

Strictly C... and perhaps we should name this numeric rather than math though?

Thanks,
Rusty.



More information about the ccan mailing list