mersenneforum.org Implementing Chinese Remainder Theorem in C
 Register FAQ Search Today's Posts Mark Forums Read

2007-11-17, 02:07   #1
ShiningArcanine

Dec 2005

22·23 Posts
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 #include 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?

 2007-11-17, 02:23 #2 ColdFury     Aug 2002 14016 Posts 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.
 2007-11-17, 02:34 #3 ShiningArcanine     Dec 2005 10111002 Posts 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
2007-11-17, 05:55   #4
ColdFury

Aug 2002

26×5 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Math 23 2017-12-15 16:46 carpetpool Miscellaneous Math 4 2017-02-09 19:26 Nick Number Theory Discussion Group 4 2016-10-31 22:26 ShiningArcanine Math 2 2007-11-17 10:01 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