у вас может быть столько же чисел, сколько у вас есть регистры или память, подумайте о умножении начальной школы. и подумайте о том, как база два упрощает это.
abcdef
* 111101
============
abcdef
000000
abcdef
abcdef
abcdef
abcdef
но что, если у меня есть только 2-битные регистры?
вы бы сделали такую вещь
ab cd ef
0 00 00 0
ab cd ef
a bc de f
ab cd ef
a bc de f
===============
, которую вы могли бы взять по две строки за раз .
Другой способ думать об этом из шестнадцатеричных чисел начальной школы. Я хочу сказать, умножить 16-битные числа, но у меня есть только 8-битная * 8-битная = 16-битная инструкция умножения
abcd * 1234 =
((ab*(2^8))+(cd*(2^0))) * ((12*(2^8))+(34*(2^0)) =
((ab*x)+(cd*y)) * ((12*x)+(34*y) =
ab*12*x*x + ab*34*x*y + cd*12*x*y + cd*34*y*y =
x и у - просто степени двух, но более того, они ставят результаты на 8 или 16 или более степеней 8-битных границ. числа теперь могут быть сделаны с умножением 8 бит * 8 бит = 16 бит или умножением 16 бит * 16 бит = 16 бит с добавленными старшими битами. затем вы отслеживаете, кто куда приземлится, есть некоторые дополнения с некоторыми переносами, которые добавляют к следующей группе.
- так вы можете использовать то, что вы знаете из школы, для каскадирования этого материала с помощью имеющихся у вас регистров / инструкций. .
Таким образом, вы могли бы построить большой множитель, и я предполагаю, что вы знаете, как каскадно сложить, или можете понять это аналогичным образом. и "просто" используйте это.
НО ваша проблема, как вы заявили. (10) * 30 ^ 19 + (10) * 30 ^ 18 и так далее.
#include <stdio.h>
int main ( void )
{
unsigned int ra;
unsigned int rb;
unsigned int rc;
for(ra=1;ra<6;ra++)
{
rc=1;
for(rb=0;rb<ra;rb++)
{
rc*=30;
}
printf("%2u 0x%08X %u\n",ra,rc,rc);
}
return(0);
}
1 0x0000001E 30
2 0x00000384 900
3 0x00006978 27000
4 0x000C5C10 810000
5 0x0172C9E0 24300000
30 - это 3 * 5 * 2. в двоичном виде она не будет выглядеть красиво, в десятичной она не будет выглядеть плохо. может быть, там есть хитрость.
abc = 10*30*30 + 11*30 + 12*0
9000 + 330 + 12
9312
я его пока не вижу.
но если подумать об этом 3,5,2
в двоичном виде x * 3 является (х << 1) + х; x * 5 - это (x << 2) + x и x * 2 = x << 1; </p>
, если десятичное число (основание 10) 1234
x = 1;
for each digit that remains in the string
x = x * 10; //shift left one number place
x = x + 2; //next digit
...
преобразование основания 10 в двоичный файл
x = 1;
x = (x<<3)+(x<<1); //x = x * 10;
x = x + 2;
x = (x<<3)+(x<<1);
x = x + 3;
x = (x<<3)+(x<<1);
x = x + 4;
или
x = 0;
x = (x<<3)+(x<<1);
x = 1;
x = (x<<3)+(x<<1);
x = x + 2;
x = (x<<3)+(x<<1);
x = x + 3;
x = (x<<3)+(x<<1);
x = x + 4;
или
x = 0;
y = x<<3;
x = y + x<<1;
x = x + 1;
y = x<<3;
x = y + x<<1;
x = x + 2;
y = x<<3;
x = y + x<<1;
x = x + 3;
y = x<<3;
x = y + x<<1;
x = x + 4;
что-то, что легко сделать из oop из базовых 30 в двоичные вместо базовых 10 в двоичный файл, как показано. Сдвигая небольшие числа, легко каскадировать столько регистров или областей памяти, сколько у вас есть места. Шаги сложения могут выполнять только один бит, так что легко каскадировать столько регистров / ячеек памяти. Таким образом, от 10 до 2 длиннее, чем у вас есть биты в регистре, не сложно. Теперь, чтобы превратить это довольно длинное двоичное число в основание 10. Да, это новая проблема.
Возможно, уловка здесь - это подход псевдо-bcd типа, один клев на десятичное число di git, и вы делать такие вещи:
1 0x0000001E 30
2 0x00000384 900
3 0x00006978 27000
4 0x000C5C10 810000
5 0x0172C9E0 24300000
"ab c" 10, 11, 12
x = 0x0
x = x * 0x30 = (x<<5) + (x << 4); //hmmm is that right?
x = x + 0x10;
...
, но для всего этого дополнения вам нужно go через право на влево и перекрывают переполнение bcd, поэтому 0x1A становится 0x20, потому что 0xA больше, чем 9 на единицу, так что это перенос одного в следующий клев. Это уродливо, но что, если бы каждый BCD di git был 8 бит?
Это путь, который я думаю, если бы вы построили себе большой регистр с большим множителем, сколько регистров / ячеек памяти было бы взять для обработки 30 ^ 19-й степени? вот насколько он должен быть большим, но если бы вы его построили, его было бы легко использовать. Чтобы получить его в двоичном формате. Теперь вы собираетесь построить большой делитель, чтобы перевести его с двоичного на базовый 10?
Это выполнимо, вы делаете это с длинным делением, стиль 10 равен 0b1010, вы действительно гуляете 101 под битами, для каждого бита вы получаете 0 или 1 его длинное деление, которое вы можете запрограммировать в любом oop Вытаскивая один бит из числителя за раз, начиная с мсбита и сравнивая, что накопление битов с 0b101 или 0b1010 будет меньше, чем в 2 раза 10, так что результат накапливает 1 или 0 и, как и при длинном делении, вы вычитаете либо 0 умножить на 10 или 1 раз на 10, как вы go.
0x1D / 10
11101
мы сбрасываем один из битов чисел за раз, как при длинном делении в аккумулятор, если вы будете сравнивать его со знаменателем
1 по сравнению с 1010 равен 0 остатку 1, следующий бит 11 по сравнению с 1010 равен 0 остатку 11 111 по сравнению с 1010 равен 0 остатку 111 1110 по сравнению с 1010 равен 1 остатку 100 1001 по сравнению с 1010 - это 0 остаток 1001
Результат равен 00010 или 2, 0x1D / 10 = 29/10 = 2, чтобы легко сделать аккумулятор, нужно всего лишь 4 бита, чтобы легко пройти один бит за раз через бесконечное количество 32-битных регистров или областей памяти. но вы должны сделать это миллион раз
1234 десятичных = 0x4D2
0x4D2 / 10 = 0x7B remainder 4
0x7B / 10 = 0xC remainder 3
0xC / 10 = 0x1 remainder 2
0x1 / 10 = 0 remainder 1
, поэтому мы сделали результат 1234 десятичных
вы начинаете с 0x4D2 и получаете 0x7B и 4 из этого, но вместо небольшого количества бит это десятки / сотни бит.
грубая сила, если вы можете сделать множитель в двоичном каскаде для нужного вам числа 32-битных слов без ошибок и тогда деление не так уж сложно кодировать. Вы можете сделать эту работу, используя умножение.
30 ^ 20 = 3,4 .. * 10 ^ 29
мой мозг не вполне понимает количество бит / слов, которое вам нужно для хранения этого числа
в любом случае, да, вы можете использовать каскадный 32-битный * 32-битный = 32-битный (16 бит за раз) или 32-битный * 32-битный = 64-битный (32 бит за раз) множитель, настолько широкий, насколько у вас есть память для (быстрое исчерпание регистров, использование регистров для умножения и сложения и добавление с переносами, использование памяти для хранения фактических чисел). заканчивая с результатом 2 базы. Затем вы можете создать длинный алгоритм деления и обрабатывать его, пока числитель не станет равным 0. Требуется ли умножение для назначения?