fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3. int	 get_polynomial_degree(int polynomial_degree);
  4. void	 get_polynomial_coefficients(int polynomial_degree, double polynomial_coefficients[]);
  5.  
  6. int  get_possible_roots_size(int polynomial_degree, double polynomial_coefficients[]);
  7. void get_possible_roots(int polynomial_degree, double polynomial_coefficients[], double possible_roots[], int a0_over_an_size);
  8. int 		get_number_of_factors_a0(double polynomial_coefficients[]);
  9. int 		get_number_of_factors_an(int polynomial_degree, double polynomial_coefficients[]);
  10. void		get_factors_a0(double polynomial_coefficients[], int factors_a0[]);
  11. void 		get_factors_an(int polynomial_degree, double polynomial_coefficients[], int factors_an[]);
  12. int 		get_a0_over_an_size(int num_factors_a0, int num_factors_an, int factors_a0[], int factors_an[]);
  13. void 		get_a0_over_an(int p_numerator[], int p_denominator[], int factors_a0[], int factors_an[], int num_factors_a0, int num_factors_an);
  14. int 		get_gcd(int num1, int num2);
  15.  
  16. int  get_rational_roots_size(int polynomial_degree, double polynomial_coefficients[], double possible_roots[], int num_possible_roots);
  17. void get_rational_roots(int polynomial_degree, double polynomial_coefficients[], double possible_roots[], int num_possible_roots, double rational_roots[]);
  18.  
  19.  
  20.  
  21. int main()
  22. {
  23. 	int i;
  24.  
  25. 	int polynomial_degree = get_polynomial_degree(polynomial_degree);
  26. 	double polynomial_coefficients[polynomial_degree];
  27. 	get_polynomial_coefficients(polynomial_degree, polynomial_coefficients);
  28.  
  29. 	int num_possible_roots = 2 * get_possible_roots_size(polynomial_degree, polynomial_coefficients);
  30. 	double possible_roots[num_possible_roots];
  31. 	get_possible_roots(polynomial_degree, polynomial_coefficients, possible_roots, num_possible_roots);
  32.  
  33.  
  34. 	printf("The input degree is: %d\n", polynomial_degree);
  35. 	printf("The input coefficients are: ");
  36. 	for(i = 0; i < polynomial_degree+1; i++)
  37. 	{
  38. 		printf("%0.4lf ", polynomial_coefficients[i]);
  39. 	}
  40. 	printf("\n");
  41.  
  42.  
  43. 	printf("There are %d possible_roots.", num_possible_roots);
  44. 	printf("The possible roots are: \n");
  45. 	for(i = 0; i < num_possible_roots; i++)
  46. 	{
  47. 		printf("%0.4lf \n", possible_roots[i]);
  48. 	}
  49. 	printf("\n"); 	
  50.  
  51. 	int num_rational_roots = get_rational_roots_size(polynomial_degree, polynomial_coefficients, possible_roots, num_possible_roots);
  52. 	double rational_roots[num_rational_roots];
  53. 	get_rational_roots(polynomial_degree, polynomial_coefficients, possible_roots, num_possible_roots, rational_roots);
  54.  
  55. 	if(num_rational_roots >= 1)
  56. 	{
  57. 		printf("The number of rational roots is: %d\n", num_rational_roots);
  58. 		printf("Root/s are: ");
  59. 		for(i = 0; i < num_rational_roots; i++)
  60. 		{
  61. 			printf("%0.4lf ", rational_roots[i]);
  62. 		}
  63. 	}
  64. 	else if(num_rational_roots == 0)
  65. 	{
  66. 		printf("There are no rational roots for this input.\n");
  67. 	}
  68.  
  69.  
  70. 	return 0;
  71. }
  72.  
  73. int get_polynomial_degree(int polynomial_degree)
  74. {
  75. 	printf("Enter the highest degree of the input polynomial: \n");
  76. 	scanf("%d", &polynomial_degree);
  77.  
  78. 	return polynomial_degree;
  79. }
  80.  
  81. void get_polynomial_coefficients(int polynomial_degree, double polynomial_coefficients[])
  82. {
  83. 	int i;
  84.  
  85. 	printf("Enter %d integer coefficients starting from 0th degree.\n", polynomial_degree+1);
  86. 	printf("Separate each input by a comma: \n");
  87. 	for(i = 0;i <= polynomial_degree; i++)
  88. 	{
  89. 		scanf("%lf, ", &polynomial_coefficients[i]);
  90. 	}
  91. }
  92.  
  93. int get_possible_roots_size(int polynomial_degree, double polynomial_coefficients[])
  94. {
  95. 	int num_factors_a0, num_factors_an;
  96. 	num_factors_a0 = get_number_of_factors_a0(polynomial_coefficients);
  97. 	num_factors_an = get_number_of_factors_an(polynomial_degree, polynomial_coefficients);
  98.  
  99. 	int factors_a0[num_factors_a0], factors_an[num_factors_an];
  100. 	get_factors_a0(polynomial_coefficients, factors_a0);
  101. 	get_factors_an(polynomial_degree, polynomial_coefficients, factors_an);
  102.  
  103. 	int i, j, gcd, size = num_factors_a0 * num_factors_an;
  104. 	for(i = 0; i < num_factors_a0;i++)
  105. 	{
  106. 		for(j = 0; j < num_factors_an;j++)
  107. 		{
  108. 			gcd = get_gcd(factors_a0[i], factors_an[j]);
  109. 			if(gcd != 1)
  110. 			{
  111. 				size--;
  112. 			}
  113. 		}
  114. 	}
  115. 	return size;
  116. }
  117.  
  118. void get_possible_roots(int polynomial_degree, double polynomial_coefficients[], double possible_roots[], int a0_over_an_size)
  119. {
  120. 	int num_factors_a0, num_factors_an;
  121. 	num_factors_a0 = get_number_of_factors_a0(polynomial_coefficients);
  122. 	num_factors_an = get_number_of_factors_an(polynomial_degree, polynomial_coefficients);
  123.  
  124. 	int factors_a0[num_factors_a0], factors_an[num_factors_an];
  125. 	get_factors_a0(polynomial_coefficients, factors_a0);
  126. 	get_factors_an(polynomial_degree, polynomial_coefficients, factors_an);
  127.  
  128. 	a0_over_an_size = get_a0_over_an_size(num_factors_a0, num_factors_an, factors_a0, factors_an);
  129. 	int p_numerator[a0_over_an_size], p_denominator[a0_over_an_size];
  130. 	get_a0_over_an(p_numerator, p_denominator, factors_a0, factors_an, num_factors_a0, num_factors_an);	
  131.  
  132.  
  133.     int i;
  134.     for (i = 0; i < a0_over_an_size; i++)
  135.     {
  136.         possible_roots[i * 2] = (double)p_numerator[i]/(double)p_denominator[i];
  137.         possible_roots[i * 2 + 1] = -(double)p_numerator[i]/(double)p_denominator[i];
  138.     }
  139. }
  140.  
  141. int get_number_of_factors_a0(double polynomial_coefficients[])
  142. {
  143. 	int divisorCount = 1, i;
  144. 	int abs_polynomial_coefficients_0 = polynomial_coefficients[0];
  145. 	abs_polynomial_coefficients_0 = fabs(abs_polynomial_coefficients_0);
  146.  
  147. 	if(abs_polynomial_coefficients_0 == 0 || abs_polynomial_coefficients_0 == 1)
  148. 	{
  149. 		return divisorCount;
  150. 	}
  151. 	else
  152. 	{
  153. 		for(i = 2; i * i < (int)abs_polynomial_coefficients_0; ++i)
  154. 		{
  155. 			if((int)abs_polynomial_coefficients_0 % i == 0)
  156. 			{
  157. 				++divisorCount;
  158. 			}
  159. 		}
  160. 		divisorCount *= 2;
  161. 		if(i * i == (int)abs_polynomial_coefficients_0)
  162. 		{
  163. 			++divisorCount;
  164. 		}
  165. 		return divisorCount;
  166. 	}
  167. }
  168.  
  169. int get_number_of_factors_an(int polynomial_degree, double polynomial_coefficients[])
  170. {
  171. 	int divisorCount = 1, i;
  172. 	int abs_polynomial_coefficients_n = polynomial_coefficients[polynomial_degree];
  173. 	abs_polynomial_coefficients_n = fabs(abs_polynomial_coefficients_n);
  174.  
  175. 	if(abs_polynomial_coefficients_n == 0 || abs_polynomial_coefficients_n == 1)
  176. 	{
  177. 		return divisorCount;
  178. 	}
  179. 	else
  180. 	{
  181. 		for(i = 2; i * i < (int)abs_polynomial_coefficients_n; ++i)
  182. 		{
  183. 			if((int)abs_polynomial_coefficients_n % i == 0)
  184. 			{
  185. 				++divisorCount;
  186. 			}
  187. 		}
  188. 		divisorCount *= 2;
  189. 		if(i * i == (int)abs_polynomial_coefficients_n)
  190. 		{
  191. 			++divisorCount;
  192. 		}
  193. 		return divisorCount;
  194. 	}
  195. }
  196.  
  197. void get_factors_a0(double polynomial_coefficients[], int factors_a0[])
  198. {
  199. 	int i, element = 0;
  200. 	int abs_polynomial_coefficients_0 = polynomial_coefficients[0];
  201. 	abs_polynomial_coefficients_0 = fabs(abs_polynomial_coefficients_0);
  202.  
  203. 	if(abs_polynomial_coefficients_0 == 0)
  204. 	{
  205. 		factors_a0[0] = 0;
  206. 	}
  207. 	else
  208. 	{
  209. 		for(i=1; i<= (int)abs_polynomial_coefficients_0; ++i)
  210. 		{
  211. 			if((int)abs_polynomial_coefficients_0%i==0)
  212. 			{
  213.  
  214. 				factors_a0[element] = i;
  215. 				element++;
  216. 			}
  217. 		}
  218. 	}
  219. }
  220.  
  221. void get_factors_an(int polynomial_degree, double polynomial_coefficients[], int factors_an[])
  222. {
  223. 	int i, element = 0;
  224. 	int abs_polynomial_coefficients_n = polynomial_coefficients[polynomial_degree];
  225. 	abs_polynomial_coefficients_n = fabs(abs_polynomial_coefficients_n);
  226. 	if(abs_polynomial_coefficients_n == 0)
  227. 	{
  228. 		factors_an[0] = 0;
  229. 	}
  230. 	else
  231. 	{
  232. 		for(i=1;i<=(int)abs_polynomial_coefficients_n;++i)
  233. 	  {
  234. 		  if((int)abs_polynomial_coefficients_n%i==0)
  235. 		  {
  236.  
  237. 				factors_an[element] = i;
  238. 				element++;
  239. 		  }
  240. 	  }
  241. 	}
  242. }
  243.  
  244. int get_a0_over_an_size(int num_factors_a0, int num_factors_an, int factors_a0[], int factors_an[])
  245. {
  246. 	int i, j, gcd, size = num_factors_a0 * num_factors_an;
  247. 	for(i = 0; i < num_factors_a0;i++)
  248. 	{
  249. 		for(j = 0; j < num_factors_an;j++)
  250. 		{
  251. 			gcd = get_gcd(factors_a0[i], factors_an[j]);
  252. 			if(gcd != 1)
  253. 			{
  254. 				size--;
  255. 			}
  256. 		}
  257. 	}
  258. 	return size;
  259. }
  260.  
  261. void get_a0_over_an(int p_numerator[], int p_denominator[], int factors_a0[], int factors_an[], int num_factors_a0, int num_factors_an)
  262. {
  263. 	int i, j, gcd, element = 0;
  264.  
  265. 	for(i = 0; i < num_factors_a0;i++)
  266. 	{
  267. 		for(j = 0; j < num_factors_an;j++)
  268. 		{
  269. 			gcd = get_gcd(factors_a0[i], factors_an[j]);
  270. 			if(gcd == 1)
  271. 			{
  272. 				p_numerator[element] = factors_a0[i];
  273. 				p_denominator[element] = factors_an[j];
  274. 				element++;
  275. 			}
  276. 		}
  277. 	}
  278. }
  279.  
  280. int get_gcd(int num1, int num2)
  281. {
  282. 	while(num1!=num2)
  283. 	{
  284. 		if(num1>num2)
  285. 			num1-=num2;
  286. 		else
  287. 			num2-=num1;
  288. 	}
  289. 	return num1;
  290. }
  291.  
  292. int  get_rational_roots_size(int polynomial_degree, double polynomial_coefficients[], double possible_roots[], int num_possible_roots)
  293. {
  294. 	int i, j, num_rational_roots = 0;
  295. 	double quotient_coefficients[polynomial_degree];
  296.  
  297. 	quotient_coefficients[0] = polynomial_coefficients[polynomial_degree];
  298. 	for(i = 0; i < num_possible_roots; i++)
  299. 	{
  300. 		for(j=1;j<=polynomial_degree;j++)
  301. 		{
  302. 			quotient_coefficients[j] = (quotient_coefficients[j-1]*possible_roots[i])+polynomial_coefficients[polynomial_degree-j];
  303. 			if(quotient_coefficients[2] == 0 && j == 2)
  304. 			{
  305. 				num_rational_roots++;
  306. 			}
  307. 		}
  308. 	}
  309. 	return num_rational_roots;
  310. }
  311.  
  312. void get_rational_roots(int polynomial_degree, double polynomial_coefficients[], double possible_roots[], int num_possible_roots, double rational_roots[])
  313. {
  314. 	int i, j, element = 0;
  315. 	double quotient_coefficients[polynomial_degree];
  316.  
  317. 	quotient_coefficients[0] = polynomial_coefficients[polynomial_degree];
  318. 	for(i = 0; i < num_possible_roots; i++)
  319. 	{
  320. 		for(j=1;j<=polynomial_degree;j++)
  321. 		{
  322. 			quotient_coefficients[j] = (quotient_coefficients[j-1]*possible_roots[i])+polynomial_coefficients[polynomial_degree-j];
  323. 			printf("Result %d = %lf\t", j, quotient_coefficients[j]);
  324. 			if(quotient_coefficients[2] == +0 || quotient_coefficients[2] == -0)
  325. 			{
  326. 				rational_roots[element] = possible_roots[i];
  327. 				printf("\nRoot %lf at i = %d, j = %d\n", rational_roots[element], i, j);
  328. 				element++;
  329. 			}
  330. 		}
  331. 		printf("\n");
  332. 	}
  333. }
Success #stdin #stdout 0s 2164KB
comments (?)
stdin
copy 
2
-2,-1,15
stdout
copy 
Enter the highest degree of the input polynomial: 
Enter 3 integer coefficients starting from 0th degree.
Separate each input by a comma: 
The input degree is: 2
The input coefficients are: -2.0000 -1.0000 15.0000 
There are 16 possible_roots.The possible roots are: 
1.0000 
-1.0000 
0.3333 
-0.3333 
0.2000 
-0.2000 
0.0667 
-0.0667 
2.0000 
-2.0000 
0.6667 
-0.6667 
0.4000 
-0.4000 
0.1333 
-0.1333 

Result 1 = 14.000000	Result 2 = 12.000000	
Result 1 = -16.000000	Result 2 = 14.000000	
Result 1 = 4.000000	Result 2 = -0.666667	
Result 1 = -6.000000	Result 2 = -0.000000	
Result 1 = 2.000000	Result 2 = -1.600000	
Result 1 = -4.000000	Result 2 = -1.200000	
Result 1 = -0.000000	Result 2 = -2.000000	
Result 1 = -2.000000	Result 2 = -1.866667	
Result 1 = 29.000000	Result 2 = 56.000000	
Result 1 = -31.000000	Result 2 = 60.000000	
Result 1 = 9.000000	Result 2 = 4.000000	
Result 1 = -11.000000	Result 2 = 5.333333	
Result 1 = 5.000000	Result 2 = 0.000000	
Result 1 = -7.000000	Result 2 = 0.800000	
Result 1 = 1.000000	Result 2 = -1.866667	
Result 1 = -3.000000	Result 2 = -1.600000	
There are no rational roots for this input.
https://ideone.com/B4uCm1
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!