fork download
copy 
  1. // Save for later.
  2.  
  3. #include <assert.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <stdio.h>
  7.  
  8. div_t floordiv(int x, int y) {
  9.     int q = x / y - ((x % y) && (x ^ y) < 0);
  10.     int r = x - y * q;
  11.     return (div_t) {q, r};
  12. }
  13.  
  14. #define INTERNAL_BASE 10
  15.  
  16. typedef struct {
  17.     int *digit;
  18.     int  count;
  19.     int  sign;
  20. } Bigint;
  21.  
  22. int _digit_add(int *x, int m, const int *y, int n)
  23. {
  24.     assert(m >= n);
  25.  
  26.     int carry = 0;
  27.     int i;
  28.  
  29.     for (i = 0; i < n; i++)
  30.     {
  31.         carry = x[i] + y[i] + carry;
  32.         x[i] = carry % INTERNAL_BASE;
  33.         carry /= INTERNAL_BASE;
  34.     }
  35.     for (; carry && i < m; i++)
  36.     {
  37.         carry = x[i] + carry;
  38.         x[i] = carry % INTERNAL_BASE;
  39.         carry /= INTERNAL_BASE;
  40.     }
  41.     return carry;
  42. }
  43.  
  44. int _digit_sub(int *x, int m, const int *y, int n)
  45. {
  46.     assert(m >= n);
  47.  
  48.     int borrow = 0;
  49.     int i;
  50.  
  51.     for (i = 0; i < n; i++)
  52.     {
  53.         borrow = x[i] - y[i] - borrow;
  54.         div_t d = floordiv(borrow, INTERNAL_BASE);
  55.         x[i] = d.rem;
  56.         borrow = d.quot & 1;
  57.     }
  58.     for (; borrow && i < m; i++)
  59.     {
  60.         borrow = x[i] - borrow;
  61.         div_t d = floordiv(borrow, INTERNAL_BASE);
  62.         x[i] = d.rem;
  63.         borrow = d.quot & 1;
  64.     }
  65.     return borrow;
  66. }
  67.  
  68. void _bigint_resize_noinit(Bigint* a, int n)
  69. {
  70.     assert(n > 0);
  71.     a->digit = realloc(a->digit, n * sizeof *a->digit);
  72.     a->count = n;
  73. }
  74.  
  75. void _bigint_resize(Bigint* a, int n, int v)
  76. {
  77.     assert(0 <= v && v < INTERNAL_BASE);
  78.  
  79.     int m = a->count;
  80.     _bigint_resize_noinit(a, n);
  81.     for (int i = m; i < n; i++)
  82.         a->digit[i] = v;
  83. }
  84.  
  85. void _bigint_append(Bigint* a, int v)
  86. {
  87.     _bigint_resize(a, a->count + 1, v);
  88. }
  89.  
  90. void _bigint_normalize(Bigint *a)
  91. {
  92.     while (a->count > 1 && a->digit[a->count-1] == 0)
  93.         a->count--;
  94.     if (a->count == 1 && a->digit[0] == 0)
  95.         a->sign = 0;
  96. }
  97.  
  98. // ..
  99.  
  100. void bigint_clear(Bigint *a)
  101. {
  102.     free(a->digit);
  103.     a->digit = 0;
  104.     a->count = 0;
  105.     a->sign  = 0;
  106. }
  107.  
  108. void bigint_init(Bigint *a)
  109. {
  110.     a->digit = 0;
  111.     a->count = 0;
  112.     a->sign  = 0;
  113.     _bigint_append(a, 0);
  114. }
  115.  
  116. void bigint_init_set_si(Bigint *a, int v)
  117. {
  118.     a->digit = 0;
  119.     a->count = 0;
  120.     a->sign  = v < 0;
  121.     do
  122.     {
  123.         _bigint_append(a, abs(v % INTERNAL_BASE));
  124.         v /= INTERNAL_BASE;
  125.     }
  126.     while (v != 0);
  127. }
  128.  
  129. void bigint_set(Bigint *a, const Bigint *b)
  130. {
  131.     _bigint_resize_noinit(a, b->count);
  132.     memmove(a->digit, b->digit, b->count * sizeof *a->digit);
  133.     a->sign = b->sign;
  134. }
  135.  
  136. void bigint_swap(Bigint *a, Bigint *b)
  137. {
  138.     Bigint t = *a; *a = *b; *b = t;
  139. }
  140.  
  141. int _bigint_compare(const Bigint *a, const Bigint *b)
  142. {
  143.     int m = a->count;
  144.     int n = b->count;
  145.     if (m != n)
  146.         return (m < n) ? -1 : 1;
  147.  
  148.     for (int i = m; i > 0; i--)
  149.     {
  150.         int x = a->digit[i-1];
  151.         int y = b->digit[i-1];
  152.         if (x != y)
  153.             return (x < y) ? -1 : 1;
  154.     }
  155.     return 0;
  156. }
  157.  
  158. void _bigint_add_lower(Bigint *c, const Bigint *a, const Bigint *b)
  159. {
  160.     if (a->count < b->count)
  161.     {
  162.         const Bigint *t = a; a = b; b = t;
  163.     }
  164.  
  165.     bigint_set(c, a);
  166.     int carry = _digit_add(c->digit, c->count, b->digit, b->count);
  167.     if (carry != 0)
  168.         _bigint_append(c, carry);
  169.     _bigint_normalize(c);
  170. }
  171.  
  172. void _bigint_sub_lower(Bigint *c, const Bigint *a, const Bigint *b)
  173. {
  174.     int sign = 0;
  175.  
  176.     if (_bigint_compare(a, b) < 0)
  177.     {
  178.         const Bigint *t = a; a = b; b = t;
  179.         sign = 1;
  180.     }
  181.  
  182.     bigint_set(c, a);
  183.     _digit_sub(c->digit, c->count, b->digit, b->count);
  184.     c->sign = sign;
  185.     _bigint_normalize(c);
  186. }
  187.  
  188. void _bigint_add_or_sub(Bigint *c, const Bigint *a, const Bigint *b, int invert)
  189. {
  190.     if ((a->sign == b->sign) ^ invert)
  191.     {
  192.         _bigint_add_lower(c, a, b);
  193.         c->sign = a->sign;
  194.     }
  195.     else
  196.     {
  197.         if (a->sign)
  198.             _bigint_sub_lower(c, b, a);
  199.         else
  200.             _bigint_sub_lower(c, a, b);
  201.     }
  202. }
  203.  
  204. void bigint_add(Bigint *c, const Bigint *a, const Bigint *b)
  205. {
  206.     _bigint_add_or_sub(c, a, b, 0);
  207. }
  208.  
  209. void bigint_sub(Bigint *c, const Bigint *a, const Bigint *b)
  210. {
  211.     _bigint_add_or_sub(c, a, b, 1);
  212. }
  213.  
  214. void bigint_print(const Bigint *a)
  215. {
  216.     if (a->sign)
  217.         putchar('-');
  218.     for (int i = a->count; i > 0; i--)
  219.         printf("%d", a->digit[i-1]); // Base-10
  220.     putchar('\n');
  221. }
  222.  
  223. // ..
  224.  
  225. void fatalerror(const char *msg)
  226. {
  227.     fprintf(stderr, "Error: %s\n", msg);
  228.     exit(1);
  229. }
  230.  
  231. int _bigint_to_si(const Bigint *a)
  232. {
  233.     int result = 0;
  234.     for (int i = a->count; i > 0; i--)
  235.     {
  236.         if (__builtin_mul_overflow(result, INTERNAL_BASE, &result) ||
  237.             __builtin_add_overflow(result, a->digit[i-1], &result))
  238.             fatalerror("overflow");
  239.     }
  240.     return a->sign ? -result : result;
  241. }
  242.  
  243. void test(int n)
  244. {
  245.     Bigint t; bigint_init(&t);
  246.  
  247.     for (int x = -n; x <= n; x++)
  248.         for (int y = -n; y <= n; y++)
  249.         {
  250.             Bigint a; bigint_init_set_si(&a, x);
  251.             Bigint b; bigint_init_set_si(&b, y);
  252.             bigint_add(&t, &a, &b);
  253.             assert(_bigint_to_si(&t) == x+y);
  254.             bigint_sub(&t, &a, &b);
  255.             assert(_bigint_to_si(&t) == x-y);
  256.             bigint_clear(&a);
  257.             bigint_clear(&b);
  258.         }
  259.  
  260.     bigint_clear(&t);
  261. }
  262.  
  263. void fibonacci(int n, Bigint *result)
  264. {
  265.     Bigint a; bigint_init_set_si(&a, 0);
  266.     Bigint b; bigint_init_set_si(&b, 1);
  267.     Bigint t; bigint_init(&t);
  268.  
  269.     for (int i = 0; i < n; i++)
  270.     {
  271.         bigint_add(&t, &a, &b);
  272.         bigint_swap(&b, &a); // a -> b
  273.         bigint_swap(&a, &t); // t -> a
  274.     }
  275.  
  276.     bigint_swap(&a, result);
  277.  
  278.     bigint_clear(&a);
  279.     bigint_clear(&b);
  280.     bigint_clear(&t);
  281. }
  282.  
  283. int main(void)
  284. {
  285.     test(123);
  286.  
  287.     Bigint a; bigint_init(&a);
  288.     Bigint b; bigint_init(&b);
  289.     Bigint c; bigint_init(&c);
  290.  
  291.     fibonacci(202, &a);
  292.     fibonacci(101, &b);
  293.  
  294.     bigint_sub(&c, &a, &b);
  295.  
  296.     bigint_print(&a);
  297.     bigint_print(&b);
  298.     bigint_print(&c);
  299.  
  300.     bigint_clear(&a);
  301.     bigint_clear(&b);
  302.     bigint_clear(&c);
  303.     return 0;
  304. }
Success #stdin #stdout 0.02s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
734544867157818093234908902110449296423351
573147844013817084101
734544867157818093234335754266435479339250
https://ideone.com/uQbd1d
language:
C (gcc 8.3)
created:
47 minutes 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!