Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 15th, 2012  |  syntax: C  |  size: 1.74 KB  |  views: 18  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define N_UINTS 5
  5. typedef struct _lp_int
  6. {
  7.         unsigned int number[N_UINTS];
  8. } lp_int;
  9.  
  10. void lpi_init_set_ui(lp_int *lpi, unsigned int initval)
  11. {
  12.         lpi->number[0] = initval;
  13.         for (int i = 1; i < N_UINTS; i++)
  14.                 lpi->number[i] = 0;
  15. }
  16.  
  17. void lpi_out_str(FILE *out, lp_int *lpi)
  18. {
  19.         for (int i = N_UINTS-1; i >= 0; i--)
  20.                 fprintf(out, "%.8X", lpi->number[i]);
  21. }
  22.  
  23. void lpi_add(lp_int *dst, lp_int *src)
  24. {
  25.         #if N_UINTS != 5
  26.         #error FIX THIS
  27.         #endif
  28.         __asm__(
  29.             "addl %1, %0;"
  30.                 "adcl %2, 4 %0;"
  31.                 "adcl %3, 8 %0;"
  32.                 "adcl %4, 12 %0;"
  33.                 "adcl %5, 16 %0;"
  34.                 "jc 0;" // Overflows crash
  35.                 : "=m"(dst->number)
  36.                 : "r"(src->number[0]), "r"(src->number[1]), "r"(src->number[2]), "r"(src->number[3]), "r"(src->number[4]));
  37. }
  38.  
  39. int main(int argc, char *argv[])
  40. {
  41.         const int denominations[] = { 1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
  42.         const int lenDenominations = sizeof(denominations)/sizeof(denominations[0]);
  43.         const int target = 9000000;
  44.  
  45.         lp_int (*table)[lenDenominations] = malloc(sizeof(lp_int)*(target+1)*lenDenominations);
  46.         for (int i = 0; i < lenDenominations; i++)
  47.                 lpi_init_set_ui(&table[target][i], 1);
  48.  
  49.         for (int sumSoFar = target-1; sumSoFar >= 0; sumSoFar--)
  50.         {
  51.                 for (int minDenomination = lenDenominations-1; minDenomination >= 0; minDenomination--)
  52.                 {
  53.                         lpi_init_set_ui(&table[sumSoFar][minDenomination], 0);
  54.                         for (int i = minDenomination; i < lenDenominations; i++)
  55.                         {
  56.                                 int newSumSoFar = sumSoFar + denominations[i];
  57.                                 if (newSumSoFar <= target)
  58.                                         lpi_add(&table[sumSoFar][minDenomination], &table[newSumSoFar][i]);
  59.                         }
  60.                 }
  61.         }
  62.  
  63.         fprintf(stdout, "Answer (hex): 0x");
  64.         lpi_out_str(stdout, &table[0][0]);
  65.         fputc('\n', stdout);
  66.  
  67.         return 0;
  68. }
clone this paste RAW Paste Data