1. C++ / Говнокод #17155

    +50

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    91. 91
    92. 92
    #include <deque>
#include <stdint.h>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
typedef uint32_t bt;
typedef uint64_t dbt;
typedef deque<bt> bn;
#define cat2(b,e) b##e
#define cat(b,e) cat2(b,e)
#define fsi(i,s,e) for(size_t i(s), cat(i,_end)(e); i<cat(i,_end); ++(i))
#define fe(i,c) for(auto i((c).begin()), cat(i,_end)((c).end()); i!=cat(i,_end); ++(i))
void ml10(bn& n){
  n.push_front(0);
}
uint32_t ni(const bn& n, size_t i){
  if(n.size()<=i)
    return 0;
  else
    return n[i];
}
size_t ms(const bn& n1, const bn& n2){
  return (max) (n1.size(), n2.size());
}
bt gr(dbt tr){
  return tr & (numeric_limits<bt>::max)();
}
bt gc(dbt tr){
  return (tr & (~((dbt)(numeric_limits<bt>::max)()))) >> (numeric_limits<bt>::digits);
}
void pb(bt b1, bt b2, bt lc, bt& r, bt& c){
  dbt tr = ((uint64_t)b1 + b2 + lc);
  r = gr(tr);
  c = gc(tr);
}
void mb(bt b1, bt b2, bt lc, bt& r, bt& c){
  dbt tr = ((uint64_t)b1 * b2 + lc);
  r = gr(tr);
  c = gc(tr);
}
bn /*constexpr*/ bi(bn n){
  reverse(n.begin(), n.end());
  return n;
}
bn pl(const bn& n1, const bn& n2){
  bn r;
  bt c=0,br=0;
  size_t ms_ = ms(n1, n2);
  //r.reserve(ms_+1);
  fsi(i,0,ms_){
    pb(ni(n1,i),ni(n2,i),c,br,c);
    r.push_back(br);
  }
  if (c)
    r.push_back(c);
  return r;
}
bn ml(bn n1, const bn& n2){
  bn lr, r;
  bt c=0;
  //r.reserve(n1.size() + n2.size() + 1);
  fsi(i2,0,n2.size()){
    fsi(i1, 0, n1.size()){
      lr.emplace_back();
      mb(n1[i1], n2[i2], c, lr[i1], c);
    }
    if (c){
      lr.push_back(c);
      c = 0;
    }
    r = pl(r, lr);
    lr.clear();
    ml10(n1);
  }
  return r;
}
#define STR1(x) #x
#define STR(x) STR1(x)
#define EXPECT_TRUE(expr)\
do{\
  if(!(expr))\
    cout<<"*****Failed test: \"" STR(expr) "\"" << endl;\
    else\
    cout << "Test OK: \"" STR(expr) "\"" << endl;\
}while(false)
#define TEST(expr)\
do{\
    cout << "Test begined: \"" STR(expr) "\"" << endl;\
    (void)(expr);\
} while (false)

    И вот мой просмотр аниме закончен.
    http://ideone.com/eRJ7FA
    main смотри в коментах

    Запостил: LispGovno, 24 Ноября 2014

    Комментарии (21) RSS

    • ava LispGovno 24.11.2014 01:25 # +1 

      int main()
{
  /*tests*/
  bt a = 0, b = 0, c = 0, r = 0;
  TEST((pb(a, b, c, r, c)));
  EXPECT_TRUE(c == 0);
  EXPECT_TRUE(r == 0);
  TEST((a = 0xffffffff, b = 0, c = 0));
  pb(a, b, c, r, c);
  EXPECT_TRUE(r == a);
  TEST((a = 0xffffffff, b = 1, c = 0));
  pb(a, b, c, r, c);
  EXPECT_TRUE(r == 0);
  EXPECT_TRUE(c == 1);
  TEST((a = 0xffffffff, b = 0xFFFFFFFF, c = 0xFFFFFFFF));
  pb(a, b, c, r, c);
  EXPECT_TRUE(r == 0xFFFFFFFD);
  EXPECT_TRUE(c == 2);
  /*tests ends*/
  cout << hex;
  cout.fill('0');
  bn v = bi(pl(bi({ 0xFFFFFFFF, 0xFFFFFFFF }), bi({ 0xFFFFFFFF, 0xFFFFFFFF })));
  fe(it, v){
    cout.width(sizeof(bt) * 2);
    cout << (unsigned)*it;
  }
  cout << endl;
  bn t = bi(ml(bi({ 0xFFFFFFFF, 0xFFFFFFFF }), bi({ 0xFFFFFFFF, 0xFFFFFFFF })));
  fe(it, t){
    cout.width(sizeof(bt) * 2);
    cout << (unsigned)*it;
  }
  cout << endl;
  return 0;
}

      В целом я проникся стилем
      Ответить

    • ava Fike 24.11.2014 04:34 # +6

      test begined [x]
      Ответить

    • ava bormand 24.11.2014 06:26 # +3

      Ну всё, еще одного заразили...
      Ответить

      • ava LispGovno 24.11.2014 09:48 # 0

        А что вам не нравится?
        В этом стиле есть что-то от хачкеля. Обычный непромышленный стиль.
        Я тут в столбик перемножаю. Получился O(n^2). Надеюсь Тарас не кинет в меня камень.
        А если бы я перемножал сложением. Сначало число плюс число. Затем 2 числа +2 числа. Затем 4 числа + 4 числа и тд... Получилось бы O(n log m), где n - число разрядов в числе, а m само число. Интересно что росло бы быстрее. Ой. Глупость спросил. Все очевидно...
        Ответить

        • ava roman-kashitsyn 24.11.2014 09:49 # 0

          > А если бы я перемножал сложением.
          DFT
          Ответить

          • ava LispGovno 24.11.2014 09:53 # 0

            Discrete Fourier transform?
            Density functional theory?
            De Financiële Telegraaf | Financieel nieuws leest u op DFT.nl?
            Department for Transport - GOV.UK?
            Ответить

            • ava roman-kashitsyn 24.11.2014 09:56 # 0

              первое, очевидно
              Ответить

              • ava LispGovno 24.11.2014 09:59 # 0

                Да кеп. Ты мне предлагаешь изучить весь курс, чтобы понять твой ответ? Обязательно изучу на досуге. Только девушку из кровати прогоню. Так и скажу ей. Ты мне больше не люба. Я хочу DFT!
                Ответить

                • ava bormand 24.11.2014 10:32 # +1

                  > девушку из кровати прогоню
                  Но ведь ГК читать она тебе не мешает...
                  Ответить

          • ava bormand 24.11.2014 10:31 # 0

            Оно вроде бы только на охрененно больших числах быстрее.

            Тогда уж какого-нибудь монтгомери, если много умножений подряд. А вообще - я ленивый распиздяй, и юзаю гмп.
            Ответить

            • ava LispGovno 24.11.2014 12:14 # 0

              гмп умеет в разные виды умножений? а что-за монтгомери метод?
              кстати мне тут намекнули что юзать библиотеки общего назначения типа gmp не секьюрно для шифрования. почему?
              Ответить

              • ava chtulhu 24.11.2014 13:22 # +1

                >кстати мне тут намекнули что юзать библиотеки общего назначения типа gmp не секьюрно для шифрования. почему?
                очистка памяти, время выполнения операций
                Ответить

              • ava bormand 24.11.2014 15:07 # 0

                > что-за монтгомери метод
                А там числа преобразовывают в немного другое представление, в котором умножение на порядок проще.

                http://en.wikipedia.org/wiki/Montgomery_reduction

                P.S. Правда я походу нагнал про его применимость, ибо там умножение по модулю.
                Ответить

                • ava 3.14159265 24.11.2014 15:10 # +1

                  У Кнута описано FFT-умножение, отлично ложащееся на регистры разрядностью 2^n.
                  Еще существует алгоритм Фюрера, но подробности его работы мне неизвестны.
                  Ответить

                  • ava bormand 24.11.2014 15:12 # +1

                    Ну FFT вроде бы только на 2^n элементов и ложится :) Даже если не для умножения юзать.

                    > алгоритм Фюрера
                    Heil, mein Führer!
                    Ответить

                    • ava 3.14159265 24.11.2014 15:16 # 0

                      Самому его реализовывать тоже не стоит. Рекомендую самонастраивающийся под задачу fftw.
                      Дизайн этой штуки впечатляет, там запилено нечто вроде самопального jitа, который генерирует код, собирает статистику и выбирает наиболее оптимальный метод расчёта.
                      PS>То что описано у Кнута по-научному зовётся schönhage-strassen algorithm.
                      Ответить

    • ava wvxvw 24.11.2014 10:33 # 0

      > 
      EXPECT_TRUE

      EXPECTO_PATRONUM(0 == 0);
      Ответить

    Добавить комментарий