mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2007-11-17, 02:07   #1
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

22·23 Posts
Default Implementing Chinese Remainder Theorem in C

I originally posted this on a programmer forum Microsoft has, but no one has replied, so I am reposting it here.

Quote:
I have implemented Chinese Remainder Theorem using some things (i.e. structures, register variables and local function prototypes) my professor mentioned in class recently to get better at C.

I realize that the sanity check has not been written yet, but assuming all user data is sane, is there any thing that I could have done better here? Also, is the binary gcd algorithm typically faster than the non-binary gcd algorithm that I used or does that depend on the processor?

Code:
#include <stdio.h>
#include <stdlib.h>

typedef struct remainder { int divisor; int residual; } remainder;

int main ( void )
{
	
	void getData ( remainder * arr, int const * const num );

	int cRT ( remainder * arr, int const * const num );

	int num;

	remainder * arr = NULL;

	/* Begin Infinite Loop */

	for (  ;  ;  )
	{

		/* Get amount of data to compute */

		printf ("Enter the quantity of data to be computed ");

		scanf ("%i", &num);

		/* Check to see if we should exit */

		if ( num <= 0 )
		{

			return 0;

		}

		/* Allocate Memory */

		arr = (remainder*)calloc (num, sizeof(remainder));

		/* Get Actual Data */

		getData(arr, &num);

		/* Check to see if data is sane */

		/* Sanity check goes here; assume all data to be sane for now */

		/* Solve for the original value and print solution */

		printf ("\nThe solution is %i.\n\n", cRT(arr, &num));

		free(arr);

	}

}

void getData ( remainder * arr, int const * const num )
{

	register int i;

	for ( i = 0; i < *num; i++ )
	{

		printf ("\nEnter divisor and residual for Chinese Remainder Theorem ");

		scanf ("%i %i", &arr[i].divisor, &arr[i].residual);

	}

}

int cRT ( remainder * arr, int const * const num )
{

	register int i, add = arr->divisor, result = arr->residual;

	int lcm ( int a, int b );

	for ( i = 1 ; i < *num ; add = lcm(add, arr[i++].divisor) )
	{

		for (  ; result % arr[i].divisor != arr[i].residual ; result += add );

	}

	return result;

}

int lcm ( int a, int b )
{

	int gcd ( int a, int b );

	return a * b / gcd ( a , b );

}

int gcd ( register int a, register int b )
{

	register int temp;

	while (b != 0)
	{

		temp = b;

		b = a % b;

		a = temp;

	}

	return a;

	/* Recursive Algorithm */
	/* return ( b == 0 ) ? a : gcd ( b, a % b ); */

}
By the way, in situations similar to add = lcm(add, arr[i++].divisor), am I the only one or are other people tempted to type add lcm= arr[i++].divisor as well?
ShiningArcanine is offline   Reply With Quote
Old 2007-11-17, 02:23   #2
ColdFury
 
ColdFury's Avatar
 
Aug 2002

14016 Posts
Default

The register keyword is extremely outdated and is ignored by all compilers. Local function prototypes are considered very bad style as well. There's no need to use calloc, when malloc would have sufficed. There's no need to pass "num" by pointer, you could just pass it by value.
ColdFury is offline   Reply With Quote
Old 2007-11-17, 02:34   #3
ShiningArcanine
 
ShiningArcanine's Avatar
 
Dec 2005

10111002 Posts
Default

Are you sure about the register keyword? I am using C89 and not C++ or C99. Also, I have been thinking about passing num as part of a structure, by using a wrapper structure around the remainder structure. I had a bad experience using malloc and I have been using calloc ever since. I will try using malloc again.

By the way, do you know how to break this up into separate files so I do not have to write the copy and paste the same functions into every program I wrote?

Edit: Malloc works. Thanks for the tip.

Last fiddled with by ShiningArcanine on 2007-11-17 at 02:37
ShiningArcanine is offline   Reply With Quote
Old 2007-11-17, 05:55   #4
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26×5 Posts
Default

Quote:
Are you sure about the register keyword?
Yes, it is totally ignored. Compilers will automatically allocate variables to registers as needed.
ColdFury is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sorting on chinese remainder theorem alpertron Math 23 2017-12-15 16:46
Complexity of Chinese Remainder Theorem carpetpool Miscellaneous Math 4 2017-02-09 19:26
Basic Number Theory 6: functions and the Chinese Remainder Theorem Nick Number Theory Discussion Group 4 2016-10-31 22:26
Chinese Remainder Problem ShiningArcanine Math 2 2007-11-17 10:01
Implementing algorithms, did I do this right? ShiningArcanine Programming 18 2005-12-29 21:47

All times are UTC. The time now is 16:20.


Sat May 28 16:20:18 UTC 2022 up 44 days, 14:21, 1 user, load averages: 1.26, 1.23, 1.38

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔