fork(1) download
copy 
  1. // Ideas
  2. // 1. Hidden header style array.
  3. // 2. Playing around with Bigint add/subtract.
  4.  
  5. #include <assert.h>
  6. #include <stddef.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <stdio.h>
  10.  
  11. // Utility.
  12.  
  13. #define SWAP(a, b) \
  14. ({ __auto_type _x = &(a); __auto_type _y = &(b); \
  15.    __auto_type _t = *_x; *_x = *_y; *_y = _t; \
  16.    (void) 0; })
  17.  
  18. div_t floordiv(int x, int y) {
  19.     int q = x / y - ((x % y) && (x ^ y) < 0);
  20.     int r = x - y * q;
  21.     return (div_t) {q, r};
  22. }
  23.  
  24. // Shadow array (private).
  25.  
  26. typedef struct {
  27.     int count, capacity;
  28. } _ArrHeader;
  29.  
  30. #define _PTR_TO_HDR(p) ((_ArrHeader*)((char*)p - sizeof(_ArrHeader)))
  31. #define _HDR_TO_PTR(h) ((void*)((char*)h + sizeof(_ArrHeader)))
  32.  
  33. void *_arr_reserve(void *p, int capacity, int itemsize)
  34. {
  35.     _ArrHeader *self = _PTR_TO_HDR(p);
  36.  
  37.     if (self->capacity < capacity)
  38.     {
  39.         self = realloc(self, itemsize*capacity + sizeof *self);
  40.         self->capacity = capacity;
  41.     }
  42.     return _HDR_TO_PTR(self);
  43. }
  44.  
  45. void *_arr_resize(void *p, int count, int itemsize)
  46. {
  47.     p = _arr_reserve(p, count, itemsize);
  48.     _PTR_TO_HDR(p)->count = count;
  49.     return p;
  50. }
  51.  
  52. void _arr_free(void *p)
  53. {
  54.     if (p != 0)
  55.         free(_PTR_TO_HDR(p));
  56. }
  57.  
  58. void *_arr_init(void)
  59. {
  60.     _ArrHeader *self = malloc(sizeof *self);
  61.     self->count = 0;
  62.     self->capacity = 0;
  63.     return _HDR_TO_PTR(self);
  64. }
  65.  
  66. void *_arr_at(void *p, ptrdiff_t i, int itemsize)
  67. {
  68.     int count = _PTR_TO_HDR(p)->count;
  69.     if (i < 0)
  70.         i += count;
  71.     assert(0 <= i && i < count);
  72.     return (char*)p + i*itemsize;
  73. }
  74.  
  75. void *_arr_append(void *p, const void *v, int itemsize)
  76. {
  77.     _ArrHeader *self = _PTR_TO_HDR(p);
  78.  
  79.     if (self->count == self->capacity)
  80.     {
  81.         int capacity = self->capacity ? 2*self->capacity : 1;
  82.         p = _arr_reserve(p, capacity, itemsize);
  83.         self = _PTR_TO_HDR(p);
  84.     }
  85.     self->count++;
  86.     memcpy(_arr_at(p, -1, itemsize), v, itemsize);
  87.     return p;
  88. }
  89.  
  90. // Shadow array (public).
  91.  
  92. #define arr_init(a) ((a) = _arr_init())
  93. #define arr_free(a) (_arr_free(a), (a) = 0)
  94. #define arr_resize(a, n) ((a) = _arr_resize(a, n, sizeof *(a)))
  95. #define arr_at(a, i) (((__typeof__(a))_arr_at(a, i, sizeof *(a)))[0])
  96. #define arr_append(a, v) ((a) = _arr_append(a, (__typeof__(*(a))[]){v}, sizeof *(a)))
  97.  
  98. void arr_pop(void *p)
  99. {
  100.     _ArrHeader *self = _PTR_TO_HDR(p);
  101.     assert(self->count > 0);
  102.     self->count--;
  103. }
  104.  
  105. void arr_clear(void *p)
  106. {
  107.     _PTR_TO_HDR(p)->count = 0;
  108. }
  109.  
  110. int arr_count(void *p)
  111. {
  112.     return _PTR_TO_HDR(p)->count;
  113. }
  114.  
  115. int arr_capacity(void *p)
  116. {
  117.     return _PTR_TO_HDR(p)->capacity;
  118. }
  119.  
  120. // Bigint.
  121.  
  122. #define INTERNAL_BASE 10
  123.  
  124. typedef struct {
  125.     int *digit;
  126.     int  sign;
  127. } Bigint;
  128.  
  129. int _digit_adc(int *x, int m, const int *y, int n, int (*op)(int, int))
  130. {
  131.     assert(m >= n);
  132.  
  133.     int carry = 0;
  134.     int i;
  135.  
  136.     for (i = 0; i < n; i++)
  137.     {
  138.         carry = op(x[i], y[i] + carry);
  139.         div_t d = floordiv(carry, INTERNAL_BASE);
  140.         x[i] = d.rem;
  141.         carry = d.quot & 1;
  142.     }
  143.     for (; carry && i < m; i++)
  144.     {
  145.         carry = op(x[i], carry);
  146.         div_t d = floordiv(carry, INTERNAL_BASE);
  147.         x[i] = d.rem;
  148.         carry = d.quot & 1;
  149.     }
  150.     return carry;
  151. }
  152.  
  153. int _op_add(int x, int y)
  154. {
  155.     return x + y;
  156. }
  157.  
  158. int _op_sub(int x, int y)
  159. {
  160.     return x - y;
  161. }
  162.  
  163. int _digit_add(int *x, int m, const int *y, int n)
  164. {
  165.     return _digit_adc(x, m, y, n, _op_add);
  166. }
  167.  
  168. int _digit_sub(int *x, int m, const int *y, int n)
  169. {
  170.     return _digit_adc(x, m, y, n, _op_sub);
  171. }
  172.  
  173. int _digit_cmp(const int *x, int m, const int *y, int n)
  174. {
  175.     if (m != n)
  176.         return (m < n) ? -1 : 1;
  177.  
  178.     for (int i = m; i > 0; i--)
  179.     {
  180.         int s = x[i-1];
  181.         int t = y[i-1];
  182.  
  183.         if (s != t)
  184.             return (s < t) ? -1 : 1;
  185.     }
  186.     return 0;
  187. }
  188.  
  189. void _bigint_normalize(Bigint *a)
  190. {
  191.     // Strip leading zeros; ensure zero is unsigned.
  192.     while (arr_count(a->digit) > 1 && arr_at(a->digit, -1) == 0)
  193.         arr_pop(a->digit);
  194.     if (arr_at(a->digit, -1) == 0)
  195.         a->sign = 0;
  196. }
  197.  
  198. void _bigint_set(Bigint* a, const Bigint* b)
  199. {
  200.     int n = arr_count(b->digit);
  201.     arr_resize(a->digit, n);
  202.     memmove(a->digit, b->digit, n * sizeof *a->digit);
  203.     a->sign = b->sign;
  204. }
  205.  
  206. void _bigint_set_si(Bigint *a, int v)
  207. {
  208.     arr_clear(a->digit);
  209.     a->sign = v < 0;
  210.  
  211.     do
  212.     {
  213.         arr_append(a->digit, abs(v % INTERNAL_BASE));
  214.         v /= INTERNAL_BASE;
  215.     }
  216.     while (v != 0);
  217. }
  218.  
  219. void _bigint_add_lower(Bigint *c, const Bigint *a, const Bigint *b)
  220. {
  221.     int m = arr_count(a->digit);
  222.     int n = arr_count(b->digit);
  223.  
  224.     if (m < n)
  225.     {
  226.         SWAP(a, b);
  227.         SWAP(m, n);
  228.     }
  229.  
  230.     _bigint_set(c, a);
  231.  
  232.     int carry = _digit_add(c->digit, m, b->digit, n);
  233.  
  234.     if (carry != 0)
  235.         arr_append(c->digit, carry);
  236.     _bigint_normalize(c);
  237. }
  238.  
  239. void _bigint_sub_lower(Bigint *c, const Bigint *a, const Bigint *b)
  240. {
  241.     int m = arr_count(a->digit);
  242.     int n = arr_count(b->digit);
  243.     int sign = 0;
  244.  
  245.     if (_digit_cmp(a->digit, m, b->digit, n) < 0)
  246.     {
  247.         SWAP(a, b);
  248.         SWAP(m, n);
  249.         sign = 1;
  250.     }
  251.  
  252.     _bigint_set(c, a);
  253.  
  254.     int borrow = _digit_sub(c->digit, m, b->digit, n);
  255.  
  256.     assert(borrow == 0);
  257.     c->sign = sign;
  258.     _bigint_normalize(c);
  259. }
  260.  
  261. void _bigint_add(Bigint *c, const Bigint *a, const Bigint *b, int bsign)
  262. {
  263.     if (a->sign == bsign)
  264.     {
  265.         _bigint_add_lower(c, a, b);
  266.         c->sign = a->sign;
  267.     }
  268.     else
  269.     {
  270.         if (a->sign)
  271.             _bigint_sub_lower(c, b, a);
  272.         else
  273.             _bigint_sub_lower(c, a, b);
  274.     }
  275. }
  276.  
  277. // Bigint (public).
  278.  
  279. void bigint_free(Bigint *a)
  280. {
  281.     arr_free(a->digit);
  282. }
  283.  
  284. void bigint_init(Bigint *a)
  285. {
  286.     a->digit = 0;
  287.     a->sign  = 0;
  288.     arr_init(a->digit);
  289.     arr_append(a->digit, 0);
  290. }
  291.  
  292. void bigint_init_set_si(Bigint *a, int v)
  293. {
  294.     a->digit = 0;
  295.     arr_init(a->digit);
  296.     _bigint_set_si(a, v);
  297. }
  298.  
  299. void bigint_set(Bigint *a, const Bigint *b)
  300. {
  301.     _bigint_set(a, b);
  302. }
  303.  
  304. void bigint_set_si(Bigint *a, int v)
  305. {
  306.     _bigint_set_si(a, v);
  307. }
  308.  
  309. void bigint_swap(Bigint *a, Bigint *b)
  310. {
  311.     Bigint t = *a; *a = *b; *b = t;
  312. }
  313.  
  314. void bigint_add(Bigint *c, const Bigint *a, const Bigint *b)
  315. {
  316.     _bigint_add(c, a, b, b->sign);
  317. }
  318.  
  319. void bigint_sub(Bigint *c, const Bigint *a, const Bigint *b)
  320. {
  321.     _bigint_add(c, a, b, !b->sign);
  322. }
  323.  
  324. void bigint_print(const Bigint *a)
  325. {
  326.     if (a->sign)
  327.         putchar('-');
  328.     for (int i = arr_count(a->digit); i > 0; i--)
  329.         printf("%d", a->digit[i-1]); // Base 10
  330.     putchar('\n');
  331. }
  332.  
  333. // Main.
  334.  
  335. void errorabort(const char *msg)
  336. {
  337.     fprintf(stderr, "Error: %s\n", msg);
  338.     exit(1);
  339. }
  340.  
  341. int _bigint_to_si(const Bigint *a)
  342. {
  343.     int result = 0;
  344.     for (int i = arr_count(a->digit); i > 0; i--)
  345.     {
  346.         if (__builtin_mul_overflow(result, INTERNAL_BASE, &result) ||
  347.             __builtin_add_overflow(result, a->digit[i-1], &result))
  348.             errorabort("overflow");
  349.     }
  350.     return a->sign ? -result : result;
  351. }
  352.  
  353. void test(int n)
  354. {
  355.     Bigint a; bigint_init(&a);
  356.     Bigint b; bigint_init(&b);
  357.     Bigint t; bigint_init(&t);
  358.  
  359.     for (int x = -n; x <= n; x++)
  360.         for (int y = -n; y <= n; y++)
  361.         {
  362.             bigint_set_si(&a, x);
  363.             bigint_set_si(&b, y);
  364.             bigint_add(&t, &a, &b);
  365.             assert(_bigint_to_si(&t) == x+y);
  366.             bigint_sub(&t, &a, &b);
  367.             assert(_bigint_to_si(&t) == x-y);
  368.         }
  369.  
  370.     bigint_free(&a);
  371.     bigint_free(&b);
  372.     bigint_free(&t);
  373. }
  374.  
  375. void fibonacci(int n, Bigint *result)
  376. {
  377.     Bigint a; bigint_init_set_si(&a, 0);
  378.     Bigint b; bigint_init_set_si(&b, 1);
  379.     Bigint t; bigint_init(&t);
  380.  
  381.     for (int i = 0; i < n; i++)
  382.     {
  383.         bigint_add(&t, &a, &b);
  384.         bigint_swap(&b, &a); // a -> b
  385.         bigint_swap(&a, &t); // t -> a
  386.     }
  387.  
  388.     bigint_swap(&a, result);
  389.  
  390.     bigint_free(&a);
  391.     bigint_free(&b);
  392.     bigint_free(&t);
  393. }
  394.  
  395. int main(void)
  396. {
  397.     test(123);
  398.  
  399.     Bigint a; bigint_init(&a);
  400.     Bigint b; bigint_init(&b);
  401.     Bigint c; bigint_init(&c);
  402.  
  403.     fibonacci(202, &a);
  404.     fibonacci(101, &b);
  405.  
  406.     bigint_sub(&c, &a, &b);
  407.  
  408.     bigint_print(&a);
  409.     bigint_print(&b);
  410.     bigint_print(&c);
  411.  
  412.     bigint_free(&a);
  413.     bigint_free(&b);
  414.     bigint_free(&c);
  415.     return 0;
  416. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
734544867157818093234908902110449296423351
573147844013817084101
734544867157818093234335754266435479339250
https://ideone.com/L56ReV
language:
C (gcc 8.3)
created:
2 days 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!