Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.10.2019, 21:27   #1
FriLDD
Пользователь
 
Регистрация: 02.10.2019
Сообщений: 10
По умолчанию Умножение двух чисел без операции умножения (Python)

подскажите, как написать программу на питоне, которая будет умножать два числа, если доступны операции: сложения, вычитания, умножение и деление на 2

про способ через циклы знаю, он бесполезен, когда нужно перемножить триллион на триллион. Главное требование к программе - скорость
Заранее спасибо
FriLDD вне форума Ответить с цитированием
Старый 10.10.2019, 22:05   #2
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

1.
Цитата:
если доступны операции: сложения, вычитания, умножение и деление на 2
Т.е. можно только умножить на 2 или разделить на два?

2. А какие числа собираетесь умножать? Целые, вещественные?

3. О каком триллионе речь? Сколь большие числа надо умножать?

4.
Код:
про способ через циклы знаю, он бесполезен, когда нужно перемножить триллион на триллион. Главное требование к программе - скорость
А если поточнее?
Если скорость, то ASM и сопроцессор вам помогут. Как это потом вставить в Питон я пока не знаю, но думаю, что решения есть.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 10.10.2019, 22:31   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Если числа целые, то меньший сомножитель можно разложить на сумму степеней двойки. Остается умножить на двойки и сложить. Как это сделать на питоне не знаю) Но цикл или его аналог все равно нужен, но это сильно короче чем складывать много раз число с самим собой
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 10.10.2019, 23:26   #4
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Все эти задачи с ограничениями - такой отстой..
Как минимум, нужна еще проверка чётности. Разрешено (m & 1) ?
Или нужно извращаться через (m /2 *2 == m) ?

Короче, для положительных чисел примерно так:
Код:
def arsch_mult(m, n):
    res = 0
    while n:
        if odd(n):
            res += m
        m *= 2
        n //= 2
    return res
Значительно чаще этот алгоритм используется для быстрого возведения в степень

Последний раз редактировалось Black Fregat; 10.10.2019 в 23:37.
Black Fregat вне форума Ответить с цитированием
Старый 12.10.2019, 13:55   #5
FriLDD
Пользователь
 
Регистрация: 02.10.2019
Сообщений: 10
По умолчанию

можно и умножать на 2, и делить на 2
числа нужно умножать любые целые, например 26468465746*456313213
то бишь огромные, ускорить это помогает умножение и деление на 2
FriLDD вне форума Ответить с цитированием
Старый 12.10.2019, 18:22   #6
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

FriLDD
Цитата:
числа нужно умножать любые целые, например 26468465746*456313213
Существуют ограничения на диапазон представляемых чисел в зависимости от типа данных.
Поищите в Гугле.
Возможно вам поможет работа не с числами, а со строковым представлением чисел. Но о скорости тут можно помолчать.
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 12.10.2019, 20:24   #7
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,529
По умолчанию

Цитата:
Сообщение от FriLDD Посмотреть сообщение
Главное требование к программе - скорость
Кажется, пора привыкнуть, но не перестаю удивляться идиотизму задаваемых иногда задач. "Главное - скорость", и поэтому нельзя применять специально сделанную для этого в процессоре аппаратную фичу.
"Нужно выиграть этап Формулы-1, но мотор на вашем болиде должен быть от 'Запорожца' "
digitalis вне форума Ответить с цитированием
Старый 14.10.2019, 03:11   #8
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Существуют ограничения на диапазон представляемых чисел в зависимости от типа данных.
Это же Python - ограничение только размером памяти
f3000.jpg
Black Fregat вне форума Ответить с цитированием
Старый 18.10.2019, 15:32   #9
FriLDD
Пользователь
 
Регистрация: 02.10.2019
Сообщений: 10
По умолчанию

Цитата:
Сообщение от digitalis Посмотреть сообщение
Кажется, пора привыкнуть, но не перестаю удивляться идиотизму задаваемых иногда задач. "Главное - скорость", и поэтому нельзя применять специально сделанную для этого в процессоре аппаратную фичу.
"Нужно выиграть этап Формулы-1, но мотор на вашем болиде должен быть от 'Запорожца' "
ну уж сорян, это проектирование алгоритмов. если хочешь полный текст задачи - вот он:
Вы один из немногих выживших в постапокалиптическом мире. Во время очередного рейда в опустошенный город вы нашли экзотический механический компьютер. К сожалению, вы обнаружили, что из арифметических операций он умеет только складывать, вычитать, умножать на 2 и делить на 2 целые числа. Но чтобы им пользоваться повседневно надо уметь умножать любые целые числа. Как это можно сделать на таком компьютере эффективно? Напишите функцию, которая выполняет умножение двух числе с использованием только +, -, << (умножение на 2) и >> (деление на 2).
FriLDD вне форума Ответить с цитированием
Старый 18.10.2019, 20:14   #10
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,529
По умолчанию

Цитата:
Сообщение от FriLDD Посмотреть сообщение
экзотический механический компьютер.
Этакий арифмометр Феликс. Со встроенным компилятором Python'а . Ну-ну...
Вот так мы сидим, озадачиваемся почесанием левой ногой правого уха, а компиляторы и ОС для нас строгают дядюшка Билл и дядюшка Радж.

Последний раз редактировалось digitalis; 18.10.2019 в 20:17.
digitalis вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Умножение беззнаковых двоичных чисел, не используя команду умножения - Assembler Evgesha200 Помощь студентам 3 09.05.2017 10:25
Программа умножения двух двоичных чисел(Pascal) chit Помощь студентам 2 19.05.2014 16:33
Просто Алгоритм умножения двух байтовых чисел Htebazile Помощь студентам 5 22.06.2013 09:12
Создание знаковых 16-разрядных целых чисел и операции умножения на ASM-51 (для микроконтроллеров MCS-51) Shark2.1 Помощь студентам 0 11.12.2010 19:01