[ccan] Mathematics Module

[Rupinder Singh]

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.

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

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
?


Thanks,
Rupinder
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/ccan/attachments/20090131/bdd5124b/attachment.htm>
-------------- next part --------------
#ifndef CCAN_CCANMATH_H
#define CCAN_CCANMATH_H

#include <stdbool.h>
#include <math.h>
#include <stdio.h>
#include <assert.h>

/**
 * is_square - Is the number a perfect square?
 * @n: number to test
 *
 * Example:
 *	if (is_square(4))
 *		printf("%d is indeed a Perfect Square!", 4);
 */
static inline bool is_square(long n)
{
    long tmp = sqrt (double(n));
    
	return tmp*tmp == n;
}

/**
 * is_prime - Is the number prime ?
 * @n: number to test
 *
 * Example:
 *	if (is_prime(17))
 *		printf("%d is Prime!\n", 17);
 */

static inline bool is_prime(unsigned long n)
{
long i;

if(n == 2)
    return 1;

if(n%2 == 0)
	return 0;

for(i=3; i*i <= n; i+=2)
	if(n%i == 0)
		return 0;

	return 1;
}

/**
 * gcd - Returns the GCD of two numbers
 * @a: first number
 * @b: second number
 * Example:
 *	if (gcd(5,7)==1)
 *		printf("gcd of 5 & 7 is 1");
 */

static inline int gcd(long a,long b)
{
    if(b==0) return (a);
    return (gcd(b,a%b));
}

/**
 * is_prime2 - Prints all the prime numbers from 2 till the target number (n)
 * Uses linked list implementation of typedef bignum for Sieve of Eratosthenes
 * @n: argument
 *
 * Example:
 *	is_prime2(7);
 *   
 *  2
 *  3
 *  5
 *	7	
 */

typedef unsigned long long bignum;

struct primerec
	{
	bignum bn;
	struct primerec * next;
	};

void printPrime(bignum bn)  // remove the 'll' that would've occured with printf("%ull", bn);
	{
	static char buf[1000];

	sprintf(buf, "%ull", bn);
	buf[strlen(buf) - 2] = '\0';
	//printf("%u\n", bn);
	printf("%s\n", buf);
	}

void freeList(struct primerec *head)
{
	struct primerec *thisPrime = head;
	while(1)
		{
		struct primerec *nextPrime = thisPrime->next;
		free(thisPrime);
		if(nextPrime == NULL)
			break;
		else
			thisPrime = nextPrime;
		}
}

void is_prime2(bignum topCandidate)
{
	printf("2\n");
	printf("3\n");
	struct primerec *firstPrime = reinterpret_cast <primerec*> (malloc(sizeof(struct primerec)));
	assert(firstPrime != NULL);
	struct primerec *latestPrime = firstPrime;
	firstPrime->bn = 5;
	firstPrime->next=NULL;
	bignum lp=5, candidate = 5;
	int inc=2,prime;
	while(candidate <= topCandidate)
		{
		struct primerec *thisPrime = firstPrime;
		prime = 1;
		while(thisPrime->bn * thisPrime->bn <= candidate)
			{
			if(candidate % thisPrime->bn == 0)
				{
				prime = 0;
				break;
				}
			thisPrime = thisPrime->next;
			}
		if(prime)
			{
			printPrime(candidate);
			//lp = candidate;
			latestPrime->next = reinterpret_cast <primerec*> (malloc(sizeof(struct primerec)));
			assert(latestPrime->next != NULL);
			latestPrime = latestPrime->next;
			latestPrime->bn = candidate;
			latestPrime->next = NULL;
			}
		candidate += inc;
		if(inc==2) inc = 4; else inc = 2;

	//	printf("%d %d\n", candidate, topCandidate);
		}

	freeList(firstPrime);
	
	//return (lp == topCandidate);

}


#endif /* CCAN_CCANMATH_H */