Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
ichs
Заблокирован
1

Быстрый алгоритм возведения в квадрат

06.03.2016, 15:44. Просмотров 829. Ответов 7
Метки нет (Все метки)

Задача. Требуется точно возвести в квадрат
целое шестизначное число. Результат представить
в виде двух чисел типа Long.
Как просто возвести в квадрат я знаю...
Но ведь умножаются РАВНЫЕ числа. Вероятно должен
существовать более быстрый алгоритм для возведения
в квадрат.
Верно ли это?
Кто может прояснить ситуацию?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.03.2016, 15:44
Ответы с готовыми решениями:

Алгоритм возведения в 4-ю степень введённого числа
Между командами ввода и вывода впишите в алгоритм несколько команд присваивания, в результате чего...

Быстрый Алгоритм поиска 2х мерного подмассива в 2х мерном массиве
Есть ли что то кроме алгоритма грубой силы, что можно тут использовать? оба массива состоят из...

Изменить программу для возведения в куб вместо возведения в квадрат
нужно изменить программу в турбо ассемблере так чтобы она не в квадрат возводила а в куб!! str1 DB...

Возведения натурального числа в квадрат
составить программу : 1^2 =1; 2^2 =1 +3; 3^2 =1 +3+5; 4^2 =1+3+5+7; ... N^2...

Макрос возведения в квадрат, куб, корень
Макрос (присвоенный кнопке) возведения в квадрат, куб, корень (именно рассчет, а не для того чтобы...

7
Evg
Эксперт CАвтор FAQ
19789 / 7429 / 560
Регистрация: 30.03.2009
Сообщений: 20,705
Записей в блоге: 30
06.03.2016, 17:04 2
Сильно подозреваю, что в задаче имелось в виду, что использовать можно только 32-битные типы. Т.е. тип, который в одно рыло не в состоянии вместить результат и результат можно записать только в две переменные такого типа
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
06.03.2016, 17:48 3
Если подразумевается, перемножить два числа, не используя в процессе умножения "регистров" большего размера... то берём функцию для умножения
C#
1
2
3
4
5
6
7
Tuple<int,int> Mult(int x, int y, int k)
{
    int a1 = x/k, b1 = x%k; // x = k*a1 + b1
    int a2 = y/k, b2 = y%k; // y = k*a2 + b2
    int c = a1*b2 + a2*b1;
    return Tuple.Create(a1*a2 + c/k, b1*b2 + (c%k)*k);
}
и упрощаем её для случая y == x
C#
1
2
3
4
5
6
Tuple<int,int> Square(int x, int k)
{
    int a1 = x/k, b1 = x%k; // x = k*a1 + b1
    int c = 2*a1*b1;
    return Tuple.Create(a1*a1 + c/k, b1*b1 + (c%k)*k);
}
0
Excalibur921
789 / 480 / 84
Регистрация: 12.10.2013
Сообщений: 3,186
08.03.2016, 18:05 4
Может сдвиг регистра?
“Битовый сдвиг можно использовать для деления и умножения на степень 2. Это работает быстрее, чем обычные арифметические операции.”
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
08.03.2016, 19:42 5
"1000" в условии сильно влияет и не даёт использовать битовый сдвиг.
0
Crystaly
8 / 8 / 0
Регистрация: 29.12.2012
Сообщений: 15
09.01.2019, 16:11 6
Да, я тоже где-то читал, вскользь упоминалось что "возведение в квадрат может быть сделано быстрее и-за повторяющихся чисел". Как именно это сделать - тоже интересно было бы узнать.
0
vantfiles
153 / 78 / 31
Регистрация: 07.05.2013
Сообщений: 279
10.01.2019, 11:08 7
Crystaly, http://ido.tsu.ru/iop_res1/teorcrypto/text/1_3.html
2
Crystaly
8 / 8 / 0
Регистрация: 29.12.2012
Сообщений: 15
10.01.2019, 17:40 8
vantfiles, Спасибо!
0
10.01.2019, 17:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2019, 17:40

Функция возведения целого числа в квадрат
Я - чайник! только начинаю программировать. препод задал задачку, выполните пожалуйста через...

Неправильный результат программы возведения в квадрат
Мы вот-вот начали изучать C++. Программирую на Visual Studio Ultimate 2013. Вот решил,...

Странный ответ в программе возведения числа в квадрат
Все доброе время суток. У меня программа выдаёт странный ответ:: Код программы такой: program...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru