Вам дана 16-битная машина и сказано, чтобы реализовать умножение целых чисел произвольного размера. Ваши регистры могут содержать только 16-битные числа, а самая большая команда умножения принимает два 8-битных входа и генерирует 16-битный результат.

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

вход

1f 4a 07
63 a3

выход

fd 66 03 a7 04

который кодирует умножение 477727 * 41827 = 19981887229.

Вы можете предположить, что последний (самый значимый) байт каждого входного номера ненулевой, а последний кусок номера, который вы выводите, должен быть ненулевым. Оба входных числа будут иметь длину не более 100 байтов.

Наименьший код выигрывает.

Помните, что наибольшее умножение, которое вам разрешено использовать, составляет 1 байт * 1 байт, и никакие целочисленные типы не должны превышать 2 байта!

Perl, 137 символов

($x,$y)=<>;while($x=~s/.. *//s){$e=hex$&;$i=0;$s=$r[$i]+=$e*hex,$r[$i]&=255,$r[++$i]+=$s>>8 for$y=~/.. */gs;$y="00$y"}printf'%02x 'x@r,@r

Предостережения

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

объяснение

Объяснение будет немного длинным, но я думаю, что большинство людей найдут его интересным.

Прежде всего, когда мне было 10 лет, меня научили следующему маленькому трюку. Вы можете умножить любые два положительных числа с этим. Я опишу это на примере 13 × 47. Вы начинаете с написания первого числа 13 и деления его на 2 (округление каждый раз), пока не достигнете 1:

13
 6
 3
 1

Теперь, рядом с 13, вы пишете другое число, 47, и продолжаете умножать его на 2 столько же раз:

13     47
 6     94
 3    188
 1    376

Теперь вы вычеркиваете все линии, где число слева чётно . В данном случае это только 6. (Я не могу сделать зачеркнутый код, поэтому я просто удалю его.) Наконец, вы добавляете все оставшиеся числа справа:

13     47
 3    188
 1    376
     ----
      611

И это правильный ответ. 13 × 47 = 611.

Теперь, поскольку вы все компьютерные гики, вы поймете, что то, что мы на самом деле делаем в левом и правом столбцах, это x >> 1и y << 1, соответственно. Кроме того, мы добавляем yтолько если x & 1 == 1. Это переводит непосредственно в алгоритм, который я напишу здесь в псевдокоде:

input x, y
result = 0
while x > 0:
    if x & 1 == 1:
        result = result + y
    x = x >> 1
    y = y << 1
print result

Мы можем переписать, ifчтобы использовать умножение, и затем мы можем легко изменить это так, чтобы оно работало побайтово, а не побитно:

input x, y
result = 0
while x > 0:
    result = result + (y * (x & 255))
    x = x >> 8
    y = y << 8
print result

Это по-прежнему содержит умножение на y, которое имеет произвольный размер, поэтому нам нужно также преобразовать его в цикл. Мы сделаем это на Perl.

Теперь переведите все на Perl:

• $xи $yявляются входными данными в шестнадцатеричном формате, поэтому они имеют младший байт первым .

• Таким образом, вместо x >> 8меня $x =~ s/.. *//s. Мне нужен пробел + звезда, потому что последний байт может не иметь пробела (может использовать пробел + ?тоже). Это автоматически помещает удаленный byte ( x & 255) в $&.

• y << 8это просто $y = "00$y".

• На resultсамом деле это числовой массив @r. В конце каждый элемент @rсодержит один байт ответа, но в середине вычисления он может содержать более одного байта. Ниже я докажу вам, что каждое значение никогда не превышает двух байтов (16 бит) и что результат всегда равен одному байту в конце.

Итак, вот код Perl, который был раскрыт и прокомментирован:

# Input x and y
($x, $y) = <>;

# Do the equivalent of $& = x & 255, x = x >> 8
while ($x =~ s/.. *//s)
{
    # Let e = x & 255
    $e = hex $&;

    # For every byte in y... (notice this sets $_ to each byte)
    $i = 0;
    for ($y =~ /.. */gs)
    {
        # Do the multiplication of two single-byte values.
        $s = $r[$i] += $e*hex,
        # Truncate the value in $r[$i] to one byte. The rest of it is still in $s
        $r[$i] &= 255,
        # Move to the next array item and add the carry there.
        $r[++$i] += $s >> 8
    }

    # Do the equivalent of y = y << 8
    $y = "00$y"
}

# Output the result in hex format.
printf '%02x ' x @r, @r

Теперь для доказательства того, что это всегда выводит байты , и что вычисление никогда не генерирует значения больше двух байтов. Я докажу это по индукции через whileцикл:

• Пустое @rв начале явно не имеет значений больше 0xFF (потому что оно вообще не имеет значений). Это завершает базовый случай.

• Теперь, учитывая, что @rв начале каждой whileитерации содержится только один байт :

  • forЦикл явно &=S все значения в результирующем массиве с 255 , за исключением последнего , так что мы только должны смотреть на этом последнем.

  • Мы знаем , что мы всегда удалить только один байт из $xи $y:

    • Следовательно, $e*hexэто умножение двух однобайтовых значений, что означает, что оно находится в диапазоне 0 — 0xFE01.

    • По индуктивной гипотезе, $r[$i]это один байт; следовательно, $s = $r[$i] += $e*hexнаходится в диапазоне 0 — 0xFF00.

    • Поэтому $s >> 8всегда один байт.

  • $yувеличивается на 00каждой итерации whileцикла:

    • Следовательно, на каждой итерации whileцикла внутренний forцикл выполняется на одну итерацию больше, чем на предыдущей whileитерации.

    • Таким образом, $r[++$i] += $s >> 8в последней итерации forцикла всегда добавляет $s >> 8к 0, и мы уже установили , что $s >> 8всегда один байт.

  • Следовательно, последнее значение, хранящееся в @rконце forцикла, также является одним байтом.

Это завершает замечательный и захватывающий вызов. Большое спасибо за публикацию!

C решение

Это решение не проверяет входные данные. Это также только слегка проверено. Скорость не была действительно рассмотрением. Память Маллока, и она не особенно умна в отношении того, сколько она захватывает. Гарантированно хватит и больше чем надо.

m () принимает строку, ожидает две строки в строке, по одному после каждого числа. Ожидаются только цифры, строчные буквы, пробелы и переводы строк. Ожидает, что шестнадцатеричные цифры всегда будут парой.

Операция умножения никогда не используется (сознательно). Сдвиг выполняется на 8-битных переменных. Выполняется одно 16-битное сложение. Нет 32-битных типов данных.

Сжатые от руки, и только мягко. edit: больше запутывания, меньше символов: D Компилируется с предупреждениями с помощью gcc.

Персонажи: 675

typedef unsigned char u8;
#define x calloc
#define f for
#define l p++
#define E *p>57?*p-87:*p-48
#define g(a) --i;--a;continue
void m(u8*d){short n=0,m=0,a,b,i,k,s;u8*t,*q,*r,*p=d,o;f(;*p!=10;n++,l){}l;f(;*p
!=10;m++,l){}t=x(n,1);q=x(m,1);r=x(n,1);p=d;a=n;i=0;f(;*p!=10;i++,l){if(*p==32){
g(a);}t[i]=E;t[i]<<=4;l;t[i]|=E;}a/=2;b=m;i=0;l;f(;*p!=10;i++,l){if(*p==32){g(b)
;}q[i]=E;q[i]<<=4;l;q[i]|=E;}b/=2;f(k=0;k<8*b;k++){if(q[0]&1){o=0;f(i=0;i<n;i++)
{s=o+t[i]+r[i];o=s>>8;r[i]=s&255;}}f(i=n;i;i--){o=t[i-1]>>7&1;t[i-1]*=2;if(i!=n)
t[i]|=o;}f(i=0;i<m;i++){o=q[i]&1;q[i]/=2;if(i)q[i-1]|=(o<<7);}}k=(r[a+b-1]==0)?a
+b-1:b+a;f(i=0;i<k;i++){printf("%02x ",r[i]);}putchar(10);}

Вы можете проверить это:

int main(void){
  m("1f 4a 07\n63 a3\n");
  m("ff ff ff ff\nff ff ff ff\n");
  m("10 20 30 40\n50 60 70\n");
  m("01 02 03 04 05 06\n01 01 01\n");
  m("00 00 00 00 00 00 00 00 00 00 00 00 01\n00 00 00 00 00 00 00 00 02\n");
  return 0;
}

Результат:

$ ./long 
fd 66 03 a7 04 
01 00 00 00 fe ff ff ff 
00 05 10 22 34 2d 1c 
01 03 06 09 0c 0f 0b 06 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 

OCaml + Батареи, 362 символа

Стандартный O (n * m) алгоритм умножения школьников. Обратите внимание, что для удовлетворения требований вызова операции выполняются с байтами строк, которые в OCaml (в данном случае удобно) являются изменяемыми. Отметим также, что аккумулятор sникогда не переполняется 16 битами, поскольку 2 (2 ^ 8 - 1) + (2 ^ 8 - 1) ^ 2 = (2 ^ 8 - 1) (2 ^ 8 + 1) = 2 ^ 16 - 1 ,

let(@)=List.map
let m a b=Char.(String.(let e s=of_list(((^)"0x"|-to_int|-chr)@nsplit s" ")in
let a,b=e a,e b in let m,n=length a,length b in let c=make(m+n)'\000'in
iteri(fun i d->let s,x=ref 0,code d in iteri(fun j e->let y=code e in
s:=!s+code c.[i+j]+x*y;c.[i+j]<-chr(!s mod
256);s:=!s/256)b;c.[i+n]<-chr!s)a;join" "((code|-Printf.sprintf"%02x")@to_list c)))

Например,

# m "1f 4a 07" "63 a3" ;;
- : string = "fd 66 03 a7 04"

# m "ff ff ff ff" "ff ff ff ff" ;;
- : string = "01 00 00 00 fe ff ff ff"

JavaScript (Node.js) , 160 байт

x=>y=>x.map((t,i)=>y.map(u=>(f=i=>(c=s[i]>>8)&&f(i++,s[i]=c+~~s[i],s[i-1]%=256))(i,s[i]=~~s[i++]+`0x${t}`*`0x${u}`)),s=[])&&s.map(t=>(t<16?0:'')+t.toString(16))

Попробуйте онлайн!

Гораздо более новый язык, чем тогда