Как получить число 17 способом умножения

Русский способ умножения

Недавно, прочитав статью на хабре Как сделать из 123456789 число 100 или 0 и решил почитать «Занимательную арифметику» Я. И. Перельмана, очень интересная книга, в которой можно кроме всего прочего узнать как работают обыкновенные счёты.

Но сегодня хотелось бы рассказать про исконно русский, как любит говорить Задорнов, метод умножения. Как известно, для того что бы умножить 2 числа, необходимо как минимум знать таблицу умножения. А ведь наши предки умели умножать и без таблицы умножения всего лишь за несколько итераций. Способ этот, не похожий на наши школьные приемы, употребителен в обиходе русских крестьян и унаследован ими из глубокой древности. Сущность его в том, что умножение любых двух чисел сводится к ряду последовательных делений одного числа пополам при одновременном удвоении другого числа.

32 X 13
16 X 26
8 X 52
4 X 104
2 X 208
1 X 416

Деление продолжают до тех пор, пока в частном не получится 1, параллельно удваивая другое число. Последнее удвоенное число и дает искомый результат. Нетрудно понять на чем этот способ основан: произведение не изменяется, если один множитель уменьшить вдвое, а другой вдвое же увеличить. Ясно поэтому, что в результате многократного повторения этой операции получается искомое произведение:

32 X 13 = 1 X 416

Однако как поступить, если при этом приходится делить пополам число нечетное?

Народный способ легко выходит из этого затруднения. Надо — гласит правило, — в случае нечетного числа откинуть единицу и делить остаток пополам; но зато к последнему числу правого столбца нужно будет прибавить все те числа этого столбца, которые стоят против нечетных чисел левого столбца: сумма и будет исходным произведением. Практически его делают так, что все строки с четными левыми числами зачеркивают; остаются только те, которые содержат слева нечетное число. Приведем пример (звездочка указывает, что данную строку надо зачеркнуть):

19 X 17
9 X 34
4 X 68*
2 X 136*
1 X 272

Сложив не зачеркнутые числа, получаем вполне правильный результат:
17 + 34 + 272 = 323.

На чем основан этот прием?

Обоснованность приема станет ясна, если принять во внимание, что
19 Х 17 = (18 + 1)17 = 18 X 17 + 17,
9 X 34 = (8 + 1)34 = 8 X 34 + 34 и т. д.
Ясно, что числа 17, 34 и т. п., утрачиваемые при делении нечетного числа пополам, необходимо прибавить к результату последнего умножения, чтобы получить произведение.

Для реализации этого метода решил написать небольшой класс, который умеет умножать «по-русски» на java с использованием операции сдвига (уж очень давно её не использовал). Не исключено, что реализовать метод можно и используя рекурсию.

Источник

10 математических секретов, которые научат легко считать в уме

Те, кто в школе относился к урокам математики с пренебрежением, наверняка хотя бы несколько раз в жизни бывали в неловкой ситуации. Как посчитать, сколько оставить на чай или сумму коммунального платежа? Если знать пару простых приёмов, это займёт у вас буквально секунду. А уж во время экзамена знание правил умножения больших чисел может помочь сэкономить критически недостающее время. «Мел» совместно с Creu делится простыми секретами вычислений.

1. Умножение на 11

Все мы знаем, что при умножении на десять к числу добавляется ноль, а знаете ли вы, что существует такой же простой способ умножения двузначного числа на 11? Вот он:

Возьмите исходное число и представьте промежуток между двумя знаками (в этом примере мы используем число 52): 5_2

Теперь сложите два числа и запишите их посередине: 5_(5+2)_2.

Таким образом, ваш ответ: 572.Если при сложении чисел в скобках получается двузначное число, просто запомните вторую цифру, а единицу прибавьте к первому числу: 9_(9+9)_9 (9+1)_8_9 10_8_9 1089. Это срабатывает всегда.

2. Быстрое возведение в квадрат

Этот приём поможет быстро возвести в квадрат двузначное число, которое заканчивается на пять. Умножьте первую цифру саму на себя +1, а в конце допишите 25. Вот и всё! 252 = (2x(2+1)) & 25

3. Умножение на пять

Большинству очень просто даётся таблица умножения на пять, но когда приходится иметь дело с большими числами, сделать это становится сложнее.

Этот приём невероятно прост. Возьмите любое число и поделите пополам. Если в результате получилось целое число, припишите ноль в конце. Если нет, не обращайте внимание на запятую и в конце добавьте пять. Это срабатывает всегда:

2682×5 = (2682 / 2) & 5 или 0

2682 / 2 = 1341 (целое число, поэтому добавьте 0)

Давайте попробуем другой пример:

2943,5 (дробное число, пропустите запятую, добавьте 5)

4. Умножение на девять

Это просто. Чтобы умножить любое число от одного до девяти на девять, посмотрите на руки. Загните палец, который соответствует умножаемому числу (например, 9×3 — загните третий палец), посчитайте пальцы до загнутого пальца (в случае 9×3 — это два), затем посчитайте после загнутого пальца (в нашем случае — семь). Ответ — 27.

5. Умножение на четыре

Это очень простой приём, хотя очевидный лишь для некоторых. Хитрость в том, что нужно просто умножить на два, а затем опять умножить на два: 58×4 = (58×2) + (58×2) = (116) + (116) = 232.

6. Подсчёт чаевых

Если вам нужно оставить 15% чаевых, есть простой способ сделать это. Высчитайте 10% (разделите число на десять), а потом добавьте получившееся число к его половине и получите ответ:

15% от $25 = (10% от 25) + ((10% от 25) / 2)

7. Сложное умножение

Если вам нужно умножать большие числа, причём одно из них — чётное, вы можете просто перегруппировать их, чтобы получить ответ:

32×125 всё равно что:

16×250 всё равно что:

8×500 всё равно что:

8. Деление на пять

На самом деле делить большие числа на пять очень просто. Нужно просто умножить на два и перенести запятую:

2. Переносим запятую: 39,0 или просто 39.

1. 2978 * 2 = 5956

9. Вычитание из 1000

Чтобы выполнить вычитание из 1000, можете пользоваться этим простым правилом. Отнимите от девяти все цифры, кроме последней. А последнюю цифру отнимите от десяти:

1. От 9 отнимите 6 = 3

2. От 9 отнимите 4 = 5

3. От 10 отнимите 8 = 2

10. Систематизированные правила умножения

Умножение на 5: Умножьте на 10 и разделите на 2.

Умножение на 6: Иногда проще умножить на 3, а потом на 2.

Умножение на 9: Умножьте на 10 и отнимите исходное число.

Умножение на 12: Умножьте на 10 и дважды прибавьте исходное число.

Умножение на 13: Умножьте на 3 и 10 раз прибавьте исходное число.

Умножение на 14: Умножьте на 7, а затем на 2.

Умножение на 15: Умножьте на 10 и 5 раз прибавьте исходное число, как в предыдущем примере.

Умножение на 16: Если хотите, 4 раза умножьте на 2. Или умножить на 8, а потом на 2.

Умножение на 17: Умножьте на 7 и 10 раз прибавьте исходное число.

Умножение на 18: Умножьте на 20 и дважды отнимите исходное число.

Умножение на 19: Умножьте на 20 и отнимите исходное число.

Умножение на 24: Умножьте на 8, а потом на 3.

Умножение на 27: Умножьте на 30 и 3 раза отнимите исходное число.

Умножение на 45: Умножьте на 50 и 5 раз отнимите исходное число.

Умножение на 90: Умножьте на 9 и припишите 0.

Умножение на 98: Умножьте на 100 и дважды отнимите исходное число.

Умножение на 99: Умножьте на 100 и отнимите исходное число.

БОНУС: проценты

Вычислить 7% от 300.

Сперва нужно понять значение слова «процент» (percent). Первая часть слова — про (per). Per = для каждого. Вторая часть — цент (cent), это как 100. Например, столетие = 100 лет. 100 центов в одном долларе и так далее. Итак, процент = для каждой сотни.

Итак, получается, что 7% от 100 будет семь. (Семь для каждой сотни, только одной сотни).

35,73% от 100 = 35,73

Но как это может быть полезным? Вернёмся к задачке 7% от 300.

7% от первой сотни равно 7. 7% от второй сотни — то же 7, и 7% от третьей сотни — все те же 7. Итак, 7 + 7 + 7 = 21. Если 8% от 100 = 8, то 8% от 50 = 4 (половина от 8).

Дробите каждое число, если нужно вычислить проценты из 100, если же число меньше 100, просто перенесите запятую влево.

8%250 =? 8 + 8 + 4 = 20,

8%25 = 2,0 (Передвигаем запятую влево).

15%300 = 15+15+15 =45

15%350 = 15+15+15+7,5 = 52,5

Также полезно знать, что вы всегда можете поменять числа местами: 3% от 100 — то же самое, что 100% от 3. А 35% от 8 — то же самое, что и 8% от 35.

Источник

Математики обнаружили идеальный способ перемножения чисел

Разбивая крупные числа на мелкие, исследователи превысили фундаментальное математическое ограничение скорости

Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его.

18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел. Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики.

«Все думают, что метод умножения, который они учили в школе, наилучший, но на самом деле в этой области идут активные исследования», — говорит Йорис ван дер Хувен, математик из Французского национального центра научных исследований, один из соавторов работы.

Сложность множества вычислительных задач, от подсчёта новых цифр числа π до обнаружения крупных простых чисел сводится к скорости перемножения. Ван дер Хувен описывает их результат как назначение своего рода математического ограничения скорости решения множества других задач.

«В физике есть важные константы типа скорости света, позволяющие вам описывать всякие явления, — сказал ван дер Хувен. – Если вы хотите знать, насколько быстро компьютеры могут решать определённые математические задачи, тогда перемножение целых чисел возникает в виде некоего базового строительного блока, по отношению к которому можно выразить такую скорость».

Почти все учатся перемножать числа одинаково. Записываем числа в столбик, перемножаем верхнее число на каждую цифру нижнего (с учётом разрядов) и складываем результат. При перемножении двух двузначных чисел приходится проделать четыре более мелких перемножения для получения итогового результата.

Школьный метод «переноса» требует выполнения n 2 шагов, где n – количество цифр в каждом из перемножаемых чисел. Вычисления с трёхзначными числами требуют девяти перемножений, а со стозначными – 10 000.

Метод переноса нормально работает с числами, состоящими из нескольких цифр, однако начинает буксовать при перемножении чисел, состоящих из миллионов или миллиардов цифр (чем и занимаются компьютеры при точном подсчёте π или при всемирном поиске больших простых чисел). Чтобы перемножить два числа с миллиардом цифр, нужно будет произвести миллиард в квадрате, или 10 18 , умножений, – на это у современного компьютера уйдёт порядка 30 лет.

Несколько тысячелетий считалось, что быстрее перемножать числа нельзя. Затем в 1960 году 23-летний советский и российский математик Анатолий Алексеевич Карацуба посетил семинар, который вёл Андрей Николаевич Колмогоров, советский математик, один из крупнейших математиков XX века. Колмогоров заявил, что не существует обобщённого способа умножения, требующего меньше, чем n 2 операций. Карацуба решил, что такой способ есть – и после недели поисков он его обнаружил.

Анатолий Алексеевич Карацуба

Умножение Карацубы заключается в разбиении цифр числа и повторной их комбинации новым способом, который позволяет вместо большого количества умножений провести меньшее количество сложений и вычитаний. Метод экономит время, поскольку на сложения уходит всего 2n шагов вместо n 2 .

Традиционный метод умножения 25х63 требует четыре умножения на однозначное число и несколько сложений

Умножение Карацубы 25х63 требует трёх умножений на однозначное число и несколько сложений и вычитаний.
a) разбиваем числа
b) перемножаем десятки
c) перемножаем единицы
d) складываем цифры
e) перемножаем эти суммы
f) считаем e – b – c
g) собираем итоговую сумму из b, c и f

При росте количества знаков в числах метод Карацубы можно использовать рекурсивно.

Традиционный метод умножения 2531х1467 требует 16 умножений на однозначное число.

Умножение Карацубы 2531х1467 требует 9 умножений.

«Сложение в школе проходят на год раньше, потому что это гораздо проще, оно выполняется за линейное время, со скоростью чтения цифр слева направо», — сказал Мартин Фюрер, математик из Пенсильванского государственного университета, создавший в 2007 быстрейший на то время алгоритм умножения.

Имея дело с крупными числами, умножение Карацубы можно повторять рекурсивно, разбивая изначальные числа почти на столько частей, сколько в них знаков. И с каждым разбиением вы меняете умножение, требующее выполнения многих шагов, на сложение и вычитание, требующие куда как меньше шагов.

«Несколько умножений можно превратить в сложения, учитывая, что с этим компьютеры будут справляться быстрее», — сказал Дэвид Харви, математик из Университета Нового Южного Уэльса и соавтор новой работы.

Метод Карацубы сделал возможным умножать числа с использованием лишь n 1,58 умножений на однозначное число. Затем в 1971 году Арнольд Шёнхаге и Фолькер Штрассен опубликовали метод, позволяющий умножать большие числа за n × log n × log(log n) небольших умножений. Для умножения двух чисел из миллиарда знаков каждое метод Карацубы потребует 165 трлн шагов.

Йорис ван дер Хувен, математик из Французского национального центра научных исследований

Метод Шёнхаге-Штрассена используется компьютерами для умножения больших чисел, и привёл к двум другим важным последствиям. Во-первых, он ввёл в использование технику из области обработки сигналов под названием быстрое преобразование Фурье. С тех пор эта техника была основой всех быстрых алгоритмов умножения.

Во-вторых, в той же работе Шёнхаге и Штрассен предположили возможность существования ещё более быстрого алгоритма – метода, требующего всего n × log n умножений на один знак – и что такой алгоритм будет наибыстрейшим из возможных. Это предположение было основано на ощущении, что у такой фундаментальной операции, как умножение, ограничение операций должно записываться как-то более элегантно, чем n × log n × log(log n).

«Большинство в общем-то сошлось на том, что умножение – это такая важная базовая операция, что с чисто эстетической точки зрения ей требуется красивое ограничение по сложности, — сказал Фюрер. – По опыту мы знаем, что математика базовых вещей в итоге всегда оказывается элегантной».

Нескладное ограничение Шёнхаге и Штрассена, n × log n × log(log n), держалось 36 лет. В 2007 году Фюрер побил этот рекорд, и всё завертелось. За последнее десятилетие математики находили всё более быстрые алгоритмы умножения, каждый из которых постепенно подползал к отметке в n × log n, не совсем достигая её. Затем в марте этого года Харви и ван дер Хувен достигли её.

Их метод является улучшением большой работы, проделанной до них. Он разбивает числа на знаки, использует улучшенную версию быстрого преобразования Фурье и пользуется другими прорывами, сделанными за последние 40 лет. «Мы используем быстрое преобразование Фурье гораздо более грубо, используем его несколько раз, а не один, и заменяем ещё больше умножений сложением и вычитанием», — сказал ван дер Хувен.

Алгоритм Харви и ван дер Хувена доказывает, что умножение можно провести за n × log n шагов. Однако он не доказывает отсутствия более быстрого метода. Гораздо сложнее будет установить, что их подход максимально быстрый. В конце февраля команда специалистов по информатике из Орхусского университета опубликовала работу, где утверждает, что если одна из недоказанных теорем окажется верной, то этот метод и вправду будет скорейшим из способов умножения.

И хотя в теории этот новый алгоритм весьма важен, на практике он мало что поменяет, поскольку лишь немного выигрывает у уже используемых алгоритмов. «Всё, на что мы можем надеяться, это на трёхкратное ускорение, — сказал ван дер Хувен. – Ничего запредельного».

Кроме того, поменялись схемы компьютерного оборудования. Двадцать лет назад компьютеры выполняли сложение гораздо быстрее умножения. Разрыв в скоростях умножения и сложения с тех пор серьёзно уменьшился, в результате чего на некоторых чипах умножение может даже обгонять сложение. Используя определённые виды оборудования, «можно ускорить сложение, заставляя компьютер умножать числа, и это какое-то безумие», — сказал Харви.

Оборудование меняется со временем, но лучшие алгоритмы своего класса вечны. Вне зависимости от того, как компьютеры будут выглядеть в будущем, алгоритм Харви и ван дер Хувена всё ещё будет самым эффективным способом умножать числа.

Источник