А какая разница какая система счисления? Арифметика везде одинаковая. Поэтому считать нужно в которой удобно. А приведение к заданной (нужно только в случае вывода результата пользователю) делается за линию.
Длинные числа удобно представлять в виде массивов.
Легкая и наглядная форма. Близка к действительному представлению числа в памяти. Автоматически резервирует место для операций умножения и сложения на возможность переполнения разряда.
Квадрат максимального числа в выбранной системе счисления должен помещаться в выбранный базовый тип. Это необходимо для хранения произведения одного разряда на другой в промежуточных вычислениях.
Выбранный базовый тип желательно брать знаковый. Это позволить избавиться от нескольких промежуточных нормализаций.
Лучше, чтобы в разряд помещалось сумма из нескольких квадратов максимального числа. Это позволит избавиться от нескольких промежуточных нормализаций.
Я с удовольствие узнаю другие методы и подходы. Подкинете?
Но ведь во встроенного действительно нет: basic и его вариации, Delphi, PHP (есть не встроенная хотя поставляется с оным), с, c++, javascript. Приведите, пожалуйста, ради расширения кругозора распространенный языке где есть встроенный.
Более верно будет предположить, что адекватно было бы применять не этот алгоритм, а с помощью БПФ.
«С каких пор оперировать битами стало медленнее, чем байтами?»
— минимально адресуемая единица памяти в x86 — байт. Соотв. для адресации битов нужно использовать дополнительные манипуляции — это раз. Два — тут действует принцип брать максимальное за раз. Например нужно умножить два 64х разрядных числа. Процессор ето может сделать это одной командой, если начать умножать побайтно или побитно, то понадобится соотв. 8 команд умножение или 64. И это только кол-во операций умножения, а еще масса других для «соединения» результата воедино. Если не верите — проведите небольшой эксперимент — напишите парочку маленьких программ на Ассемблере.
«Это дает лишний расход памяти в 4 раза.»
— откуда Вы взяли число 4? В этом случае гораздо больше. 4 будет если взять за основание системы счисления 2^16, а размер базового типа 2^64. И то это расход только на само хранение. Еще куча места выделяется во время подсчета. Кстати, такую организацию памяти придумал не я, если для Вас ето будет аргументом. Так принято хранить длинные числа.
«Вы храните массив цифр в порядке разрядов десятичного числа.»
«Вы путаете основание системы счисления с разрядностью двоичного числа»
— Да нет. Обратите внимание на
#define BASE 10 //система счисления
. Например, число 16400 можно представить в виде a[] = {0,0,4,6,1}, если основание системы 10. А если основание, допустим, 12000, то число примет вид a[] = {4400, 1}
Наверное, в этом месте плохо построено предложение. Там где «на порядок», идет речь про сравнение операции сложения с операций умножения.
А насчет именно «на порядок» не спорую, цель была подчеркнуть отношение между ними как n^1 / n ^ 2. Просто в голове не нашлось правильного описания для данного отношения.
В статье наоборот написано, что реально нужно использовать не десятичную систему. Например, если процессор/среда разработки предоставляет возможность умножения двух 32-х чисел и сложения 64-х битных, то разумно будет выбрать за основание системы счисления значение около 2^30. «Потери» памяти вприоритет у скорости решения, а не в занимаемой памяти
А насчет двоичной не совсем понятно, что Вы имеете ввиду. Выделить участок памяти и оперировать непосредственно битами? — медленно и к тому же экономия памяти в этих задачах неприоритетна — или хранить в массиве двоичные цифры? — тоже медленно и слишком расточительно (поэтому еще медленнее).
А где Вы взяли изначальное количество операций умножения равное двум? Попробуйте два двух- трех-значных числа умножить в столбик у потом посчитать количество операция умножения относительно кол-ва цифр
Даже если в обоих числах по 100 знаков, то наивное умножение потребует 100*100 операций умножения, а сложение — 100 сложения. Это не учитывая того, что операция умножения сама по себе дольше выполняется процессором.
Формула написана и в той статье на Хабре. Вы похоже не учли мой прошлый комментарий. Статья писалась «поделиться с общественностью в доступной форме» и никак не претендует на краткость и тп.
1. С умением гуглить у меня все нормально — как видите алгоритм был разобран.
2. Мне нужен был не код, а алгоритм. А прочитать готовы текст куда проще, чем разбирать исходник.
3. Под «беглый поиск в google ничего путнего не дал» имелось ввиду: «Русскоязычных статей с простым и детальным изложение найти не удалось (Википедию не считаю т.к. лично для меня там материал сложный). Поэтому пришлось собирать по-частям информацию из русскоязычных и англоязычных источников.»
PS не подумайте, что огрызаюсь — просто мне показалось Вы не совсем уловили суть.
Что-то винегрет получается. Чем же тогда этот способ плох, если он отлично подходит для этой системы?
Легкая и наглядная форма. Близка к действительному представлению числа в памяти. Автоматически резервирует место для операций умножения и сложения на возможность переполнения разряда.
Я с удовольствие узнаю другие методы и подходы. Подкинете?
— почему же?
Более верно будет предположить, что адекватно было бы применять не этот алгоритм, а с помощью БПФ.
— откуда Вы взяли число 4? В этом случае гораздо больше. 4 будет если взять за основание системы счисления 2^16, а размер базового типа 2^64. И то это расход только на само хранение. Еще куча места выделяется во время подсчета. Кстати, такую организацию памяти придумал не я, если для Вас ето будет аргументом. Так принято хранить длинные числа.
— Да нет. Обратите внимание на . Например, число 16400 можно представить в виде a[] = {0,0,4,6,1}, если основание системы 10. А если основание, допустим, 12000, то число примет вид a[] = {4400, 1}
А насчет именно «на порядок» не спорую, цель была подчеркнуть отношение между ними как n^1 / n ^ 2. Просто в голове не нашлось правильного описания для данного отношения.
А насчет двоичной не совсем понятно, что Вы имеете ввиду. Выделить участок памяти и оперировать непосредственно битами? — медленно и к тому же экономия памяти в этих задачах неприоритетна — или хранить в массиве двоичные цифры? — тоже медленно и слишком расточительно (поэтому еще медленнее).
Извиняюсь. Ошибки исправлены. Спасибо.
2. Мне нужен был не код, а алгоритм. А прочитать готовы текст куда проще, чем разбирать исходник.
3. Под «беглый поиск в google ничего путнего не дал» имелось ввиду: «Русскоязычных статей с простым и детальным изложение найти не удалось (Википедию не считаю т.к. лично для меня там материал сложный). Поэтому пришлось собирать по-частям информацию из русскоязычных и англоязычных источников.»
PS не подумайте, что огрызаюсь — просто мне показалось Вы не совсем уловили суть.