fork(1) download
copy 
  1. // Ranlux24.
  2. // These are probably too clunky to be generally useful.
  3. // @todo Consolidate to a single class.
  4.  
  5. #include <stdlib.h>
  6. #include <limits.h>
  7. #include <assert.h>
  8. #include <stdio.h>
  9. #include <time.h>
  10.  
  11. // Utility.
  12.  
  13. #define unlikely(c) \
  14.     __builtin_expect(!!(c), 0)
  15.  
  16. #define BITS(x) \
  17.     (sizeof(x) * CHAR_BIT)
  18.  
  19. #define NEW_T(T, count) \
  20.     ((T *) allocate(count * sizeof(T)))
  21.  
  22. void *allocate(size_t n)
  23. {
  24.     void *r = malloc(n);
  25.     assert(r != 0 || n == 0);
  26.     return r;
  27. }
  28.  
  29. // EngineBase.
  30.  
  31. typedef struct EngineBase {
  32.     int  (*next)    (struct EngineBase*);
  33.     void (*discard) (struct EngineBase*, int);
  34.     void (*delete)  (struct EngineBase*);
  35. } EngineBase;
  36.  
  37. int nextEngineBase(EngineBase *self)
  38. {
  39.     return self->next(self);
  40. }
  41.  
  42. void discardEngineBase(EngineBase *self, int n)
  43. {
  44.     return self->discard(self, n);
  45. }
  46.  
  47. void deleteEngineBase(EngineBase *self)
  48. {
  49.     return self->delete(self);
  50. }
  51.  
  52. // SubtractWithCarry.
  53.  
  54. typedef struct {
  55.     EngineBase base;
  56.     int *x, c, i, m, r, s;
  57. } SubtractWithCarryEngine;
  58.  
  59. static inline int next_(int *x, int mask, int i_s, int i_r, int *carry)
  60. {
  61.     int y = x[i_s] - x[i_r] - *carry;
  62.     *carry = -(y >> (BITS(int)-1));
  63.     return y & mask;
  64. }
  65.  
  66. int nextSubtractWithCarryEngine(EngineBase *base)
  67. {
  68.     SubtractWithCarryEngine* self = (SubtractWithCarryEngine *) base;
  69.  
  70.     self->i = self->i + 1;
  71.     int *x = self->x, i = self->i, r = self->r;
  72.  
  73.     if (unlikely(i >= r))
  74.     {
  75.         int *c = &self->c, m = self->m, s = self->s, t = r - s;
  76.  
  77.         for (int i = 0; i < s; i++)
  78.             x[i] = next_(x, m, i + t, i, c);
  79.         for (int i = s; i < r; i++)
  80.             x[i] = next_(x, m, i - s, i, c);
  81.         self->i = i = 0;
  82.     }
  83.     return x[i];
  84. }
  85.  
  86. void discardSubtractWithCarryEngine(EngineBase *self, int n)
  87. {
  88.     for (int i = 0; i < n; i++)
  89.         nextSubtractWithCarryEngine(self);
  90. }
  91.  
  92. void deleteSubtractWithCarryEngine(EngineBase *self)
  93. {
  94.     free(self);
  95. }
  96.  
  97. EngineBase *newSubtractWithCarryEngine(int w, int s, int r)
  98. {
  99.     assert(0 < w && w < BITS(int));
  100.     assert(0 < s && s < r);
  101.  
  102.     SubtractWithCarryEngine *self = NEW_T(SubtractWithCarryEngine, 1);
  103.  
  104.     self->base.next = nextSubtractWithCarryEngine;
  105.     self->base.discard = discardSubtractWithCarryEngine;
  106.     self->base.delete = deleteSubtractWithCarryEngine;
  107.     self->x = NEW_T(int, r);
  108.     self->c = 0;
  109.     self->i = r-1;
  110.     self->m = -1U >> (BITS(int) - w);
  111.     self->r = r;
  112.     self->s = s;
  113.  
  114.     for (int i = 0; i < r; i++)
  115.         self->x[i] = rand() & self->m;
  116.     return (EngineBase *) self;
  117. }
  118.  
  119. // DiscardBlock.
  120.  
  121. typedef struct {
  122.     EngineBase base, *owned;
  123.     int p, r, i;
  124. } DiscardBlockEngine;
  125.  
  126. int nextDiscardBlockEngine(EngineBase *base)
  127. {
  128.     DiscardBlockEngine *self = (DiscardBlockEngine *) base;
  129.  
  130.     if (self->i == 0)
  131.     {
  132.         discardEngineBase(self->owned, self->p - self->r);
  133.         self->i = self->r;
  134.     }
  135.     self->i -= 1;
  136.     return nextEngineBase(self->owned);
  137. }
  138.  
  139. void deleteDiscardBlockEngine(EngineBase *base)
  140. {
  141.     DiscardBlockEngine *self = (DiscardBlockEngine *) base;
  142.  
  143.     if (self != 0)
  144.     {
  145.         deleteEngineBase(self->owned);
  146.         free(self);
  147.     }
  148. }
  149.  
  150. EngineBase *newDiscardBlockEngine(EngineBase **unique, int p, int r)
  151. {
  152.     assert(0 < r <= p);
  153.  
  154.     DiscardBlockEngine *self = NEW_T(DiscardBlockEngine, 1);
  155.  
  156.     self->base.next = nextDiscardBlockEngine;
  157.     self->base.discard = 0;
  158.     self->base.delete = deleteDiscardBlockEngine;
  159.     self->owned = *unique; *unique = 0; // Transfer ownership.
  160.     self->p = p;
  161.     self->r = r;
  162.     self->i = r;
  163.     return (EngineBase *) self;
  164. }
  165.  
  166. // Ranlux24.
  167.  
  168. EngineBase *newRanlux24(void)
  169. {
  170.     EngineBase *ranlux24_base = newSubtractWithCarryEngine(24, 10, 24);
  171.     return newDiscardBlockEngine(&ranlux24_base, 223, 23);
  172. }
  173.  
  174. int main(void)
  175. {
  176.     srand(time(0));
  177.     EngineBase *ranlux24 = newRanlux24();
  178.  
  179.     for (int i = 0; i < 24; i++)
  180.     {
  181.         int r = nextEngineBase(ranlux24);
  182.         printf("%d\n", r);
  183.     }
  184.     deleteEngineBase(ranlux24);
  185.     return 0;
  186. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9643487
13087343
9002981
2728608
6440861
16162890
11103592
6328646
5486537
16471102
14576468
170176
1456147
5762612
12145564
5048967
1374604
8593875
5973521
4356939
2718259
11802128
7114838
4821637
https://ideone.com/D9U9Tf
language:
C (gcc 8.3)
created:
10 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!