Еще вопрос в раздел головоломки, связанный с историей выч.техники.
Был такой спецпроцессор для баллистических вычислений, оперирующий 32-разрядными целыми.
Для ускорения работы представление чисел было экзотическим: число представлялось в виде 8-ми 4-х битных остатков от деления на 8 простых чисел.
Соответственно, при арифметических операциях работали 8 простых 4-х битных "параллельных" процессора с таблицами решений - очень быстро и просто.
Внимание вопросы:
1.Как выбрать простые числа для однозначного представления чисел?
2.Как перевести число из такого представления в классическое 32-х разрядное целое беззнаковое?
Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице. Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.
20-05-2007 10:20 | Комментарий к предыдущим ответам
Yashin:
Я так понимаю, что для 32-х битного числа простые числа должны выбираться из условия: a1*a2*a3*a4*a5*a6*a7*a8=2^32 ?
Жжоте! :) Попробуйте, для разнообразия, разложить число 2^32 на множители :))
По сути задачи - в основе лежит Китайская теорема об остатках (кстати, числа не обязаны быть простыми - достаточно их _взаимной_ простоты).
У Кнута по этой системе счисления есть во втором томе целый раздел (4.3.2 "Модулярная арифметика", издание 2000-го года).
И в Википедии кое-что тоже есть (включая алгоритм Евклида для перевода в обычную систему): http://en.wikipedia.org/wiki/Residue_number_system http://en.wikipedia.org/wiki/Chinese_remainder_theorem
(есть и русская статья про теорему, но она урезанная)
Из преимуществ такой системы Кнут пишет про быстроту умножений в такой системе (сложность порядка O(n) вместо стандартной O(n^2)) плюс возможность распараллеливания вычислений. Из минусов - сложность операций сравнения, проверки переполнения и деления.
>>>Я одного не понимаю, как это все ускоряет счичление.
Фокус в том, что любая операция сводится к операциям над остатками, а их можно вычислять паралельно. Более того, любая бинарная операция на четырехразрядном процессоре производится крайне просто: заранее составляется таблица результатов (всего 256 вариантов) для которой ключем служат значения операндов - любое действие сводимое к операциям над остатками за один такт!
30-04-2007 06:14 | Комментарий к предыдущим ответам
при арифметических операциях работали 8 простых 4-х битных "параллельных" процессора
Эти процики - специализированные. Числа складываются покомпонентно, и никаких входящих переносов... Такой способ представления при подобных операциях выигрывает целую кучу времени, в отличии от обычных алгоритмов сложения, а тем более на одном процессоре...
Правда есть и серьезные недостатки:
1) Тяжело сравнивать числа
2) Сложные алгоритмы деления/умножения
3) Невозможность представить дробное число
B1*a1=B2*a2=....=Bn*an
Спросоня описался. Конечно же правильно B1*p1+a1=B2*p2+a1=... , где
p1 - основание,
а1 - остаток
29-04-2007 23:24 | Комментарий к предыдущим ответам
1) подбирать в циклах B1, B2, ..., Bn до тех пор пока не выполняется B1*a1=B2*a2=....=Bn*an (неужели так трудно придумать этот способ?)
2) или же использовать приведенный ранее метод
29-04-2007 09:33 | Комментарий к предыдущим ответам
а как по нормальному?
Пришлось раскопать свою старую тетрадь, т.к. я не помню самого рационального метода перевода((...
И вот что там есть:
A = a1*B1+a2*B2+…+an*Bn-r*P (1)
(a1, …, an - соответствующие остатки)
P = p1*p2*...*pn
r = 0, 1, 2,… (целые числа)
(r такое, что разность между левой и правой частью выражения (1) была меньше P)
Bi = (P/pi)*ki, где ki = 1, 2, …, pi
(ki такое, что остаток от деления (Bi mod pi)=1)
Ну вот есть число (1, 1) в системе [3, 5].
A = 1*B1+1*B2-r*P;
P = 3*5 = 15;
B1 = (P/p1)*k1, подставляем вместо k1 2 ( 15*2/3 mod 3=1 ), получим
B1 = (15/3)*2 = 10;
B2 = (P/p2)*k2, подставляем вместо k2 2 ( 15*2/5 mod 5=1 ), получим
B2 = (15/5)*2 = 6;
A = 1*10+1*6-r*15, подставляем вместо r 1 ( 16-1*15=1<15 ), получим
A = 16-15 = 1;
29-04-2007 05:08 | Комментарий к предыдущим ответам
Это уже никому не надо, это было раньше. Задача из раздела головоломки, а я не автор, пытаюсь вместе с вами разобраться в решении вопроса. А как числа переводить обратно? если использовать таблицу, то нужно 2^32*4 = 17гб памяти. а как по нормальному?
29-04-2007 01:42 | Комментарий к предыдущим ответам
тогда минимальные простые числа из условия это -
5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 > 2^32
5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 < 2^32. вам надо брать [7, 11, 13, 17, 19, 23, 29, 31]. Кстати, числоо оснований можно уменьшить за счет увеличения их значений.
И еще подумайте, а надо ли вам использовать такую систему счисления? Диапозон представления такой же как и Cardinal, а мароки с операциями - больше. Кстати, оперции здесь отличаются от операций 10-ой системы счисления.
число представлялось в виде 8-ми 4-х битных остатков
Создатели такой машины брали основания близкие, но не большие, числа 255. Это позволяло максимально эффективно использовать память, а также значительно увеличить границы представления чисел...
28-04-2007 14:47 | Комментарий к предыдущим ответам
Ой что-то я перемудрил:
Function CardToBall(c:Cardinal):Cardinal;
begin
Result:= (c mod 5 shl 28) or (c mod 7 shl 24)
or (c mod 11 shl 20) or (c mod 13 shl 16)
or (c mod 17 shl 12) or (c mod 19 shl 8)
or (c mod 23 shl 4) or (c mod 29);
end;
28-04-2007 14:42 | Комментарий к предыдущим ответам
Function CardToBall(c:Cardinal):Cardinal;
begin
Result:= (c and $0FFFFFFF mod 5 shl 28) or (c and $F0FFFFFF mod 7 shl 24)
or (c and $FF0FFFFF mod 11 shl 20) or (c and $FFF0FFFF mod 13 shl 16)
or (c and $FFFF0FFF mod 17 shl 12) or (c and $FFFFF0FF mod 19 shl 8)
or (c and $FFFFFF0F mod 23 shl 4) or (c and $FFFFFFF0 mod 29);
end;
28-04-2007 12:30 | Комментарий к предыдущим ответам
Такая система называется системой счисления в остаточных классах. Основания выбираютсчя совершенно произвольным образом: самое главное здесь чтобы они были ПРОСТЫМИ числами. ПРОСТЫЕ числа выбраны для ВЗАИМНОЙ ОДНОЗНАЧНОСТИ, т.е. одному числу - одно представление.
Колличество выбраных оснований[простых чисел] характеризует диапозон представляемых значений....
По поводу перевода числа. На самом деле это очень сложная задача. Раньше для таких случаев существовали специальные таблицы: посмотрел число - увидел представление, и наоборот.... Поскольку таких таблиц у вас нету, то придется, наверно, методом перебора....
Ну и вот примерчик решил написать.....
Берем 2 простых числа: [3, 5]. Здесь необходимо помнить в каком порядке у вас идут основания(но обычно в естественном), чтоб правильно число обратно перевести. Тогда число 1 10-ой сис-мы счисления в нашей сис-ме будет иметь вид (1 mod 3, 1 mod 5)=(1, 1). Если же теперь мы попытаемся представить число 16 10-ой сис-мы счисления, то тоже получим (1, 1). Вывод: вышли за границу представления чисел, поэтому необходимо ввсети еще одно основание.....
Пусть у нас имеетюся следующие основания: [a1, a2, .... , an]. Тогда в такой сис-ме мы можем представить числа из диапозона (0, X], где Х=a1*a2*...*an.
Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Функция может не работать в некоторых версиях броузеров.
