То, что вы делаете, действительно круто. И как это происходит, я могу немного рассказать о том, как реализовать дробные логарифмы, используя только целочисленное сложение и вычитание! Этот пост будет длинным, но в нем будет много деталей, а в конце - рабочая реализация, и этого должно быть достаточно для того, чтобы вы поработали с вашим странным механическим компьютером.
Сравнение реализации
Вам нужно уметь сравнивать числа. В то время как вы сказали, что можете выполнять сравнения == 0 и> 0, этого не достаточно для большинства интересных алгоритмов, которые вы хотите реализовать. Вам нужны относительные сравнения, которые можно определить с помощью вычитания:
isLessThan(a, b):
diff = b - a
if diff > 0 then return true
else return false
isGreaterThan(a, b):
diff = a - b
if diff > 0 then return true
else return false
isLessThanOrEqual(a, b):
diff = a - b
if diff > 0 then return false
else return true
isGreaterThanOrEqual(a, b):
diff = b - a
if diff > 0 then return false
else return true
В оставшейся части этого поста я просто напишу более простую форму a > b, но если вы не можете сделать это напрямую, вы можете заменить одну из операций выше.
Реализация смены
Теперь, поскольку у вас нет оборудования для сдвига цифр, вам придется создавать «подпрограммы» для его реализации. Сдвиг влево очень прост: добавьте номер к себе, и снова, и снова, а затем добавьте исходный номер, а затем добавьте его еще раз; и это эквивалентно сдвигу влево на 1 цифру.
Итак, сдвиг влево на одну цифру или умножение на десять:
shiftLeft(value):
value2 = value + value
value4 = value2 + value2
value5 = value4 + value
return value5 + value5
Сдвиг на несколько цифр - это просто повторный вызов shiftLeft():
shl(value, count):
repeat:
if count <= 0 then goto done
value = shiftLeft(value)
count = count - 1
done:
return value
Сдвиг вправо на одну цифру немного сложнее: нам нужно сделать это с повторным вычитанием и сложением, как в псевдокоде ниже:
shr(value, count):
if count == 0 then return value
index = 11
shifted = 0
repeat1:
if index < 0 then goto done
adder = shl(1, index - count)
subtractor = shl(adder, count)
repeat2:
if value <= subtractor then goto next
value = value - subtractor
shifted = shifted + adder
goto repeat2
next:
index = index - 1
goto repeat1
done:
return count
Удобно, поскольку с самого начала трудно смещаться вправо, алгоритм позволяет нам непосредственно выбирать, на сколько цифр сместиться.
Умножение
Похоже, ваше оборудование может иметь умножение? Но если это не так, вы можете реализовать умножение, используя повторное сложение и сдвиг. Двоичное умножение является самой простой формой реализации, которая на самом деле эффективна, и для этого необходимо, чтобы мы сначала внедрили multiplyByTwo() и divideByTwo(), используя те же базовые методы, которые мы использовали для реализации shiftLeft() и shr().
После того, как они реализованы, умножение включает в себя многократное срезание последнего бита одного из чисел, а если этот бит равен 1, то добавление растущей версии другого числа к промежуточному итогу:
multiply(a, b):
product = 0
repeat:
if b <= 0 then goto done
nextB = divideByTwo(b)
bit = b - multiplyByTwo(nextB)
if bit == 0 then goto skip
product = product + a
skip:
a = a + a
b = nextB
goto repeat
done:
return product
Полная реализация этого приведена ниже, если вам это нужно.
Целочисленные логарифмы
Мы можем использовать нашу способность сдвигаться вправо на цифру, чтобы вычислить целое число часть логарифма числа-10 числа - это действительно просто, сколько раз вы можете сдвинуть число прямо перед вами достичь числа, слишком маленького, чтобы его сдвинуть.
integerLogarithm(value):
count = 0
repeat:
if value <= 9 then goto done
value = shiftRight(value)
count = count + 1
goto repeat
done:
return count
Так что для 0-9 это возвращает 0; для 10-99 это возвращает 1; для 100-999 это возвращает 2 и т. д.
Целочисленные экспоненты
Противоположность вышеприведенному алгоритму довольно тривиальна: чтобы вычислить 10, возведенное в целую степень, мы просто сместим цифры, оставленные степенью.
integerExponent(count):
value = shl(1, count)
return value
Так что для 0 это возвращает 1; для 1 это возврат 10; для 2 это возвращает 100; для 3 это возвращает 1000; и т. д.
Разделение целого числа и дроби
Теперь, когда мы можем обрабатывать целочисленные степени и логарифмы, мы почти готовы обрабатывать дробную часть. Но прежде чем мы действительно сможем поговорить о том, как вычислить дробную часть логарифма, мы должны поговорить о том, как разделить задачу, чтобы мы могли вычислить дробную часть отдельно от целочисленной части. В идеале мы хотим иметь дело только с вычислением логарифмов для чисел в фиксированном диапазоне - скажем, от 1 до 10, а не от 1 до бесконечности.
Мы можем использовать наши процедуры целочисленного логарифма и экспоненты, чтобы нарезать задачу полного логарифма так, чтобы мы всегда имели дело со значением в диапазоне [1, 10), независимо от того, какое входное число было.
Сначала мы вычисляем целочисленный логарифм, а затем целочисленный показатель, а затем вычитаем его из исходного числа.Все, что осталось, - это дробная часть, которую нам нужно вычислить: и тогда единственное оставшееся упражнение - это смещение этой дробной части, чтобы она всегда находилась в согласованном диапазоне.
normalize(value):
intLog = integerLogarithm(value) // From 0 to 12 (meaningful digits)
if intLog <= 5 then goto lessThan
value = shr(value, intLog - 5)
goto done
lessThan:
value = shl(value, 5 - intLog)
done:
return value
Вы можете убедить себя относительнобез особых усилий, что независимо от того, какое было исходное значение, его наибольшая ненулевая цифра будет перемещена в столбец 7: таким образом, «12345» станет «000000123450» (т. е. «0000001.23450»).Это позволяет нам делать вид, что всегда есть невидимая десятичная точка чуть больше, чем наполовину ниже числа, так что теперь нам нужно только решить проблему вычисления логарифмов значений в диапазоне [1, 10).
(Почему «больше, чем на полпути»? Нам понадобится, чтобы верхняя половина значения всегда была равна нулю, и вы поймете, почему через мгновение.)
Дробные логарифмы
Кнут объясняет, как это сделать, в Искусство компьютерного программирования, , раздел 1.2.2.Наша цель состоит в том, чтобы вычислить log10 (x), чтобы для некоторых значений b1, b2, b3 ..., где n уже 0 (потому что мы разбили целую часть выше):
log10 (x) = n + b1 / 2 + b2 / 4 + b3 / 8 + b4 / 16 + ...
Кнут говорит, что мы можемполучить b1, b2, b3 ... как это:
Чтобы получить b1, b2, ..., мы теперь устанавливаем x0 = x / 10 ^ n и, дляk> = 1,
b [k] = 0, x [k] = x [k-1] ^ 2, если x [k-1] ^ 2 <10; </p>
b [k] = 1, x [k] = x [k-1] ^ 2/10, если x [k-1] ^ 2> = 10.
То естькаждый шаг использует цикл псевдокода примерно так:
fractionalLogarithm(x):
for i = 1 to numberOfBinaryDigitsOfPrecision:
nextX = x * x
if nextX < 10 then:
b[i] = 0
else:
b[i] = 1
nextX = nextX / 10
Для того, чтобы это работало с использованием чисел с фиксированной точкой, которые у нас есть выше, мы должны реализовать x * x, используя сдвиг, чтобы переместить десятичную точку назадна место, которое потеряет несколько цифр.Это приведет к распространению ошибки, как говорит Кнут, но даст достаточную точность, достаточную для демонстрационных целей.
Таким образом, учитывая дробное значение, сгенерированное normalize(value), мы можем вычислить его дробный двоичный логарифм какэто:
fractionalLogarithm(value):
for i = 1 to 20:
value = shr(value * value, 6)
if value < 1000000 then:
b[i] = 0
else:
b[i] = 1
value = shr(value, 1)
Но двоичный дробный логарифм - отдельные биты!- не особенно полезен, тем более что мы вычислили десятичную версию целочисленной части логарифма на предыдущем шаге.Таким образом, мы изменим это еще раз, чтобы вычислить дробный логарифм десятичный , до пяти раз, вместо вычисления массива битов;для этого нам понадобится таблица из 20 значений, которые представляют преобразования каждого из этих битов в десятичную, и мы также будем хранить их как фиксированные:
table[1] = 1/(2^1) = 1/2 = 500000
table[2] = 1/(2^2) = 1/4 = 250000
table[3] = 1/(2^3) = 1/8 = 125000
table[4] = 1/(2^4) = 1/16 = 062500
table[5] = 1/(2^5) = 1/32 = 031250
table[6] = 1/(2^6) = 1/64 = 015625
...
table[17] = 1/(2^17) = 1/131072 = 000008
table[18] = 1/(2^18) = 1/262144 = 000004
table[19] = 1/(2^19) = 1/514288 = 000002
table[20] = 1/(2^20) = 1/1048576 = 000001
Так что теперь с этимВ таблице мы можем получить весь дробный логарифм, используя чистую целочисленную математику:
fractionalLogarithm(value):
log = 0
for i = 1 to 20:
value = shr(value * value, 6)
if value >= 1000000 then:
log = log + table[i]
value = shr(value, 1)
return log
Собираем все вместе
Наконец, для полного логарифмалюбое целое число, которое может представлять ваша машина, это все, что вычислит логарифм с шестизначной точностью в форме «0000XX.XXXXXX»:
log(value):
intPart = integerLogarithm(value)
value = normalize(value)
fracPart = fractionalLogarithm(value)
result = shl(intPart, 6) + fracPart
return result
Демонстрация
Чтобы показать, что математика работает - и что она работает довольно хорошо!- ниже - реализация вышеупомянутого алгоритма на JavaScript.Здесь используется чистая целочисленная математика: только сложение, вычитание и относительное сравнение.Функции используются для организации кода, но они ведут себя как подпрограммы: они не являются рекурсивными и не очень глубоко вкладывают.
Вы можете попробовать его вживую (нажмите кнопку «Выполнить» и введите 12345 в поле ввода).Сравните результат со стандартной функцией Math.log(), и вы увидите, насколько близка чистая целочисленная версия:
function shiftLeft(value) {
var value2 = value + value;
var value4 = value2 + value2;
var value5 = value4 + value;
return value5 + value5;
}
function shl(value, count) {
while (count > 0) {
value = shiftLeft(value);
count = count - 1;
}
return value;
}
function shr(value, count) {
if (count == 0) return value;
var index = 11;
var shifted = 0;
while (index >= 0) {
var adder = shl(1, index - count);
var subtractor = shl(adder, count);
while (value > subtractor) {
value = value - subtractor;
shifted = shifted + adder;
}
index = index - 1;
}
return shifted;
}
//-----------------------------------
function multiplyByTwo(value) {
return value + value;
}
function multiplyByPowerOfTwo(value, count) {
while (count > 0) {
value = value + value;
count = count - 1;
}
return value;
}
function divideByPowerOfTwo(value, count) {
if (count == 0) return value;
var index = 39; // lg(floor(pow(10, 12)))
var shifted = 0;
while (index >= 0) {
var adder = multiplyByPowerOfTwo(1, index - count);
var subtractor = multiplyByPowerOfTwo(adder, count);
while (value >= subtractor) {
value = value - subtractor;
shifted = shifted + adder;
}
index = index - 1;
}
return shifted;
}
function divideByTwo(value) {
return divideByPowerOfTwo(value, 1);
}
function multiply(a, b) {
var product = 0;
while (b > 0) {
nextB = divideByTwo(b);
bit = b - multiplyByTwo(nextB);
if (bit != 0) {
product += a;
}
a = a + a;
b = nextB;
}
return product;
}
//-----------------------------------
var logTable = {
"1": 500000,
"2": 250000,
"3": 125000,
"4": 62500,
"5": 31250,
"6": 15625,
"7": 7813,
"8": 3906,
"9": 1953,
"10": 977,
"11": 488,
"12": 244,
"13": 122,
"14": 61,
"15": 31,
"16": 15,
"17": 8,
"18": 4,
"19": 2,
"20": 1,
};
//-----------------------------------
function integerLogarithm(value) {
var count = 0;
while (value > 9) {
value = shr(value, 1);
count = count + 1;
}
return count;
}
function normalize(value) {
var intLog = integerLogarithm(value);
if (intLog > 5)
value = shr(value, intLog - 5);
else
value = shl(value, 5 - intLog);
return value;
}
function fractionalLogarithm(value) {
var log = 0;
for (i = 1; i < 20; i++) {
var squaredValue = multiply(value, value);
value = shr(squaredValue, 5);
if (value >= 1000000) {
log = log + logTable[i];
value = shr(value, 1);
}
}
return log;
}
function log(value) {
var intPart = integerLogarithm(value);
value = normalize(value);
var fracPart = fractionalLogarithm(value);
var result = shl(intPart, 6) + fracPart;
return result;
}
//-----------------------------------
// Just a little jQuery event handling to wrap a UI around the above functions.
$("#InputValue").on("keydown keyup keypress focus blur", function(e) {
var inputValue = Number(this.value.replace(/[^0-9]+/g, ''));
var outputValue = log(inputValue);
$("#OutputValue").text(outputValue / 1000000);
var trueResult = Math.floor((Math.log(inputValue) / Math.log(10)) * 1000000 + 0.5) / 1000000
$("#TrueResult").text(trueResult);
});
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
Input integer: <input type="text" id="InputValue" /><br /><br />
Result using integer algorithm: <span id="OutputValue"></span><br /><br />
True logarithm: <span id="TrueResult"></span><br />