Algorithms_in_C 1.0.0
Set of algorithms implemented in C.
Loading...
Searching...
No Matches
Macros | Functions
sol1.c File Reference

Problem 26 solution More...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
Include dependency graph for sol1.c:

Macros

#define MAX_DENO   2000
 limit of unit fractions
 
#define MAX_LEN    (MAX_DENO + 10)
 length of resulting recurring fraction number
 

Functions

int compare (const void *a, const void *b)
 comparison function for use with internal qsort algorithm
 
int main (int argc, char *argv[])
 Main function.
 

Detailed Description

Problem 26 solution

Author
Krishna Vedala

Macro Definition Documentation

◆ MAX_LEN

#define MAX_LEN    (MAX_DENO + 10)

length of resulting recurring fraction number

19{
20 return (*(unsigned short *)a - *(unsigned short *)b);
21}
22
23/** Main function */
24int main(int argc, char *argv[])
25{
26 unsigned short max_digits = 0, max_idx_number = 0;
27
28 clock_t start_time = clock();
29 short deno;
30#ifdef _OPENMP
31#pragma omp for
32#endif
33 for (deno = 2; deno < MAX_DENO; deno++)
34 {
35 unsigned short remainders[MAX_LEN];
36 unsigned short rem = 1, *rem_ptr = remainders;
37 memset(remainders, (unsigned short)-1,
38 MAX_LEN * sizeof(unsigned short));
39 // remainders[0] = 1;
40 // printf("1/%-4u\t ", deno);
41 unsigned short index = 0, num_digits;
42
43 while (rem != 0)
44 {
45 rem = (rem * 10) % deno;
46 if (rem == 0)
47 {
48 index = 0;
49 break;
50 }
51 rem_ptr = (unsigned short *)bsearch(
52 &rem, remainders, MAX_LEN, sizeof(unsigned short), compare);
53 // printf("%2d, ", rem);
54 // printf("(%14p), ", rem_ptr);
55 if (rem_ptr != NULL)
56 break;
57 remainders[index] = rem;
58 rem_ptr = remainders;
59 index++;
60 }
61
62 num_digits = index - (rem_ptr - remainders);
63 // printf("\n\t(%14p, %14p, %4u, %4u)\n", rem_ptr, remainders, index,
64 // num_digits);
65#ifdef _OPENMP
66#pragma omp critical
67 {
68#endif
69 if (num_digits > max_digits)
70 {
71 max_digits = num_digits;
72 max_idx_number = deno;
73 // printf("\t (%u, %u)\n ", max_digits, max_idx_number);
74 }
75#ifdef _OPENMP
76 }
77#endif
78 }
79 clock_t end_time = clock();
80
81 printf("Time taken: %.4g ms\n",
82 1e3 * (double)(end_time - start_time) / CLOCKS_PER_SEC);
83 printf("Maximum digits: %hu\t Denominator: %hu\n", max_digits,
84 max_idx_number);
85
86 return 0;
87}
main
int main()
Main function.
Definition sol1.c:12
MAX_DENO
#define MAX_DENO
limit of unit fractions
Definition sol1.c:14
MAX_LEN
#define MAX_LEN
length of resulting recurring fraction number
Definition sol1.c:15
compare
int compare(const void *a, const void *b)
comparison function for use with internal qsort algorithm
Definition sol1.c:19

Function Documentation

◆ compare()

int compare ( const void *  a,
const void *  b 
)

comparison function for use with internal qsort algorithm

20{
21 return (*(unsigned short *)a - *(unsigned short *)b);
22}

◆ main()

int main ( int  argc,
char *  argv[] 
)

Main function.

26{
27 unsigned short max_digits = 0, max_idx_number = 0;
28
29 clock_t start_time = clock();
30 short deno;
31#ifdef _OPENMP
32#pragma omp for
33#endif
34 for (deno = 2; deno < MAX_DENO; deno++)
35 {
36 unsigned short remainders[MAX_LEN];
37 unsigned short rem = 1, *rem_ptr = remainders;
38 memset(remainders, (unsigned short)-1,
39 MAX_LEN * sizeof(unsigned short));
40 // remainders[0] = 1;
41 // printf("1/%-4u\t ", deno);
42 unsigned short index = 0, num_digits;
43
44 while (rem != 0)
45 {
46 rem = (rem * 10) % deno;
47 if (rem == 0)
48 {
49 index = 0;
50 break;
51 }
52 rem_ptr = (unsigned short *)bsearch(
53 &rem, remainders, MAX_LEN, sizeof(unsigned short), compare);
54 // printf("%2d, ", rem);
55 // printf("(%14p), ", rem_ptr);
56 if (rem_ptr != NULL)
57 break;
58 remainders[index] = rem;
59 rem_ptr = remainders;
60 index++;
61 }
62
63 num_digits = index - (rem_ptr - remainders);
64 // printf("\n\t(%14p, %14p, %4u, %4u)\n", rem_ptr, remainders, index,
65 // num_digits);
66#ifdef _OPENMP
67#pragma omp critical
68 {
69#endif
70 if (num_digits > max_digits)
71 {
72 max_digits = num_digits;
73 max_idx_number = deno;
74 // printf("\t (%u, %u)\n ", max_digits, max_idx_number);
75 }
76#ifdef _OPENMP
77 }
78#endif
79 }
80 clock_t end_time = clock();
81
82 printf("Time taken: %.4g ms\n",
83 1e3 * (double)(end_time - start_time) / CLOCKS_PER_SEC);
84 printf("Maximum digits: %hu\t Denominator: %hu\n", max_digits,
85 max_idx_number);
86
87 return 0;
88}
Here is the call graph for this function: