Форум программистов, компьютерный форум CyberForum.ru

Быстро возвести в квадрат число заданной длины (<16 байт) - C++

Восстановить пароль Регистрация
 
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
01.06.2013, 01:37     Быстро возвести в квадрат число заданной длины (<16 байт) #1
Нужно быстро возвести в квадрат число заданной длины (<16 байт). Лучшее, что я пока придумал -- это делить число на 2 маленьких по формуле: http://www.cyberforum.ru/cgi-bin/latex.cgi?(a+bx)^2=2(\frac 12a^2+abx+\frac 12b^2x^2), где умножение, деление на 2 -- просто сдвиг на 1. Я сначала делю, а потом умножаю, чтоб в месте http://www.cyberforum.ru/cgi-bin/latex.cgi?abx не было переполнения. Тут http://www.cyberforum.ru/cgi-bin/latex.cgi?x=2^{32}. После этого я числа http://www.cyberforum.ru/cgi-bin/latex.cgi?a^2, b^2 считаю по такой же формуле (рекуррентно), а числа http://www.cyberforum.ru/cgi-bin/latex.cgi?ab считаю просто в столбик. Для чисел больше 16 байт я использую алгоритм Карацубы. Есть ли более эффективный алгоритм возведения в квадрат?
Заранее спасибо!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
drdrink
39 / 39 / 1
Регистрация: 13.05.2013
Сообщений: 103
01.06.2013, 09:53     Быстро возвести в квадрат число заданной длины (<16 байт) #2
vlad_light, Я думаю что лучше для чисел меньше 16 байт не будет,
ты насколько я понял работаешь с большими числами, и наверно ты их представляешь в виде, an*B^n + ... + a1*B^1 + a0*B^0, где B - основание системы счисления, а можно узнать каков размер твоей базы?
у меня просто имеется алгоритм быстрого возведения в квадрат, для больших чисел с базой unsigned short то есть 16 бит, если такой же размер у тебя то я могу поделиться своим кодом=)
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
01.06.2013, 10:56     Быстро возвести в квадрат число заданной длины (<16 байт) #3
А в результате должно получиться число < 32 байт? Какие типы данных ты используешь?
drdrink
39 / 39 / 1
Регистрация: 13.05.2013
Сообщений: 103
01.06.2013, 12:13     Быстро возвести в квадрат число заданной длины (<16 байт) #4
lazybiz, ну как бы если число < 16 байт то получится меньше 32 байт
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
01.06.2013, 13:47     Быстро возвести в квадрат число заданной длины (<16 байт) #5
vlad_light, я всегда считал, и продолжаю считать, что самый эфективный способ возведения в квадрат — умножение числа на самого себя.

Если нужна длинная арифметика (тогда ты неправильно сформулировал условия), то используй быстрое проебразование Фурье, лучшего результата на практике ты вряд ли достигнешь.
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
01.06.2013, 15:08  [ТС]     Быстро возвести в квадрат число заданной длины (<16 байт) #6
а можно узнать каков размер твоей базы?
у меня просто имеется алгоритм быстрого возведения в квадрат, для больших чисел с базой unsigned short то есть 16 бит
Поделись, пожалуйста! У меня размер базы 32 бита (беззнаковый инт)
Какие типы данных ты используешь?
Использую типа unsigned unt и unsigned long long для переносов при суммировании (хотя можно и без него, но к скорости это прироста не даст).
Если нужна длинная арифметика
я же написал, что числа около 16 байт Вот у меня, например, БПФ работает медленнее, чем алгоритм Карацубы. Он начинает выигрывать на числах порядка 1 миллиона бит, а такие я не использую.
drdrink
39 / 39 / 1
Регистрация: 13.05.2013
Сообщений: 103
01.06.2013, 17:42     Быстро возвести в квадрат число заданной длины (<16 байт) #7
Цитата Сообщение от vlad_light Посмотреть сообщение
Поделись, пожалуйста! У меня размер базы 32 бита (беззнаковый инт)

Использую типа unsigned unt и unsigned long long для переносов при суммировании (хотя можно и без него, но к скорости это прироста не даст).
я же написал, что числа около 16 байт Вот у меня, например, БПФ работает медленнее, чем алгоритм Карацубы. Он начинает выигрывать на числах порядка 1 миллиона бит, а такие я не использую.
32 это ты зря, потому что тебе как раз нужны будут 16 бит, специально для переносов, а unsigned long long для переносов получается некорректно, сам пробовал сначала такой тип, но убедился что работает неправильно

Добавлено через 2 минуты
iama, не соглашусь с тобой, есть алгоритмы работающие быстрее чем умножение само на себя, я имею ввиду чисел длинной до 70 тысяч бит, после 100 я думаю самый оптимальный алгоритм, это алгоритм Шёнгахе-Штрассена, как раз использующий в себе БПФ
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
01.06.2013, 17:52  [ТС]     Быстро возвести в квадрат число заданной длины (<16 байт) #8
а unsigned long long для переносов получается некорректно
быть не может Какая разница 16 и 32 бит или 32 и 64?
Скинь код возведение в квадрат, пожалуйста)
drdrink
39 / 39 / 1
Регистрация: 13.05.2013
Сообщений: 103
01.06.2013, 21:05     Быстро возвести в квадрат число заданной длины (<16 байт) #9
vlad_light, не ну я не знаю, просто когда я использовал unsigned long long то когда возникал перенос, то есть в более старшей стоял битик либо 0 либо 1, то он оставшиеся биты заполнял как попало, и работа происходила некорректно

Добавлено через 4 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void BigN::Sqr(const BigN& a)
{
    int n = a.GetLen(); // GetLen() - возвращает длину числа в базах
    Destroy();
    Array(2*n);  //  выделение памяти 2*n баз
    D_BASE tmp = 0, mask = 1 << (2*BASE_SIZE - 1), tmp1 = 0, r = 0xffffffff; // D_BASE - unsigned long, BASE_SIZE - 16;
    BASE u = 0, v = 0, carry = 0; // BASE - unsigned short
    BASE *aw = a.al, *bw = al;   // al - указатель на младшую базу числа
    for(int i = 0; i < n; i++)
    {
        tmp = *(bw + 2*i) + (*(aw + i))*(*(aw + i));
        u = tmp >> BASE_SIZE;
        v = (BASE)tmp;
        *(bw + 2*i) = v;
        carry = 0;
        for(int j = i + 1; j < n; j++)
        {
            tmp = 0;
            tmp = (*(aw + i))*(*(aw + j));
            tmp1 = *(bw + i + j) + (carry*(1 << BASE_SIZE) + u);
            if((tmp & mask) == 0)
            {
                if(tmp1 > r - 2*tmp)
                    carry = 1;
                else carry = 0;
            }
            else carry = 1;
            tmp = 2*tmp + tmp1;
            u = tmp >> BASE_SIZE;
            v = (BASE)tmp;
            *(bw + i + j) = v;
        }
        tmp = 0;
        tmp = *(bw + i + n + 1)*(1 << BASE_SIZE) + *(bw + i + n) + (carry*(1 << BASE_SIZE) + u);
        *(bw + i + n + 1) = tmp >> BASE_SIZE;
        *(bw + i + n) = (BASE)tmp;
    }
    ar = ah;  // ar - указатель на старшую базу, ah - указатель на конец выделенной памяти
    for(;*ar == 0 && ar > al; --ar)  // Нормализация числа
    {}
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.06.2013, 16:02     Быстро возвести в квадрат число заданной длины (<16 байт)
Еще ссылки по теме:

C++ не могу возвести в квадрат)
C++ Найти первое число в строке, возвести его в квадрат и вывести
Возвести в квадрат некоторые элементы массива C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
02.06.2013, 16:02  [ТС]     Быстро возвести в квадрат число заданной длины (<16 байт) #10
Можешь затестить, какая быстрее работает?
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <ctime>
 
typedef unsigned int int32;
typedef unsigned long long int64;
 
const int SQUARE_CUTOFF = 1 + (1 << 4);
 
const int mask = 1 << 31;
 
void mult (const int32* number1, const int32* number2, const int length1, const int length2, int32* product);
void sqr (const int32* number, const int length, int32* square);
 
int main ()
{
    const int size = 64;
    const int iter = 100000;
    clock_t time;
 
    int32 a[size] = {0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF};
    int32 b[size] = {0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,
                     0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF,0xFFFFFFFF, 0xFFFFFFFF, 0xFAFFFFFF, 0xFFFFFFFF};
    int32 c[size << 1], d[size * 3 + 1];
 
    time = clock ();
 
    for (int i = 0; i < iter; ++i)
        mult (a, b, size, size, c);
 
    time = clock () - time;
 
    std::cout << "Simple multiplication:\t\t" << (double) time / iter;
 
    time = clock ();
 
    for (int i = 0; i < iter; ++i)
        sqr (a, size, d);
 
    std::cout << std::endl;
 
    time = clock () - time;
 
    std::cout << "Modified multiplication:\t" << (double) time / iter;
 
    for (int i = 0; i < (size << 1); ++i)
        if (c[i] != d[i])
            std::cerr << "ERROR!";
 
    std::cin.get ();
 
    return 0;
}
 
 
void mult (const int32* number1, const int32* number2, const int length1, const int length2, int32* product)
{
    memset (product, 0, (length1 + length2) * sizeof (int32));
 
    int64 currentSum;
    int32 carry = 0;
 
    for (int i = 0; i < length2; ++i)
    {
        carry = 0;
 
        for (int j = 0; j < length1; ++j)
        {
            currentSum = (int64) number1[j] * number2[i] + product[i + j] + carry;
            product[i + j] = (int32) currentSum;
            carry = currentSum >> 32;
        }
 
        product[i + length1] += carry;
    }
}
 
void sqr (const int32* multiplier, const int length, int32* square)
{
    if (length < SQUARE_CUTOFF)
    {
        mult (multiplier, multiplier, length, length, square);
 
        return;
    }
 
    int64 current_sum, carry = 0;
 
    const int32* multiplierLow = &multiplier[0];
    const int32* multiplierHigh = &multiplier[length >> 1];
 
    int32* productLow = &square[0];
    int32* productHigh = &square[length];
    int32* productMid = &square[length << 1];
 
    sqr (multiplierLow, length >> 1, productLow);
    sqr (multiplierHigh, length >> 1, productHigh);
    mult (multiplierLow, multiplierHigh, length >> 1, length >> 1, productMid);
 
    square[length + (length >> 1)] += productMid[length - 1] >> 31;
 
    for (int i = length - 1; i > 0; --i)
    {
        productMid[i] <<= 1;
 
        if (productMid[i - 1] >> 31)
            ++productMid[i];
    }
 
    productMid[0] <<= 1;
 
    for (int i = 0; i < length; ++i)
    {
        current_sum = (int64) square[i + (length >> 1)] + productMid[i] + carry;
        square[i + (length >> 1)] = current_sum;
        carry = current_sum >> 32;
    }
 
    square[length + (length >> 1)] += carry;
}
Yandex
Объявления
02.06.2013, 16:02     Быстро возвести в квадрат число заданной длины (<16 байт)
Ответ Создать тему
Опции темы

Текущее время: 03:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru