用于计算三角函数，对数或类似内容的算法.仅加减 [英] Algorithm for calculating trigonometry, logarithms or something like that. ONLY addition-subtraction
问题描述
我正在恢复Ascota 170古董机械可编程计算机.它已经在工作了.现在，我正在寻找一种算法来证明其功能-例如计算三角表或对数表.或类似的东西.不幸的是，从数学运算来看，计算机只能加和减整数(-1E12至1E12中的55个寄存器).甚至没有移位到数字的运算-因此可以通过编程将其实现为仅乘以非常小的数字.但是它的逻辑运算已经非常完善.
您能告诉我任何合适的算法吗?
所以您正在做的事情确实很棒.碰巧的是，我可以解释很多关于如何仅使用整数加法和减法来实现分数对数的方法！这篇文章会很长，但是其中包含很多细节，最后还有一个可行的实现，对于您用怪异的机械计算机做一些有趣的事情应该足够了.
实施比较
您将需要能够比较数字.虽然您说可以执行== 0和> 0的比较，但对于您要实现的大多数有趣算法来说，这还远远不够.您需要相对比较，可以通过减法确定:
isLessThan(a，b):差异= b-a如果diff>0，然后返回true否则返回假isGreaterThan(a，b):差异= a-b如果diff>0，然后返回true否则返回假isLessThanOrEqual(a，b):差异= a-b如果diff>0，然后返回false否则返回trueisGreaterThanOrEqual(a，b):差异= b-a如果diff>0，然后返回false否则返回true 在本文的其余部分中，我将只编写 a>的更简单形式.b ，但是如果您不能直接执行此操作，则可以替换上述操作之一.
实施班次
现在，由于您没有数字移位硬件，因此必须创建例程"来实现它.左移很容易:给自己加上一个数字，一次又一次，然后加上原始数字，然后再加上一次.这相当于向左移一位.
因此向左移动一位数字，或乘以十:
shiftLeft(value):值2 =值+值值4 =值2 +值2值5 =值4 +值返回值5 +值5 多次移位只是重复调用 shiftLeft():
shl(值，计数):重复:如果计数< = 0，则转到完成值= shiftLeft(值)计数=计数-1完毕:返回值 向右移动一位数字会有点困难:我们需要反复进行减法和加法运算，如下面的伪代码所示:
shr(值，计数):如果count == 0，则返回值指数= 11转移= 0重复1:如果索引<0然后转到完成加法器= shl(1，索引-计数)减法器= shl(加法器，计数)重复2:如果值< =减法器，则转到下一个值=值-减法器移位=移位+加法器转到重复2下一个:索引=索引-1转到重复1完毕:退货计数 方便的是，由于一开始很难向右移动，因此该算法使我们可以直接选择要移动的位数.
乘法
看来您的硬件可能有乘法?但是，如果没有，您可以使用重复的加法和移位来实现乘法.二进制乘法是最有效的最简单实现形式，它要求我们首先使用与以前相同的基本技术来实现 multiplyByTwo()和 divideByTwo()实现 shiftLeft()和 shr().
一旦实现了这些，乘法就涉及重复切出其中一个数字的最后一位，如果该位是 1 ，然后将另一个数字的递增版本添加到运行中总计:
multiply(a，b):产品= 0重复:如果b< = 0，则转到完成nextB = dividByTwo(b)位= b-multipliByTwo(nextB)如果bit == 0，则跳转产品=产品+ a跳过:a = a + ab =下一个重复完毕:退货 如果需要的话，下面将提供完整的实现.
整数对数
我们可以使用向右移动一位数字的能力来计算数字的以10为底的对数的整数部分-实际上，这是您可以将数字右移多少次您得到的数字太小而无法移动.
integerLogarithm(值):计数= 0重复:如果值< = 9，则转到完成值= shiftRight(值)计数=计数+ 1重复完毕:退货计数 因此对于0-9，这将返回0；对于0-9，则返回0.对于10-99，则返回1；对于10-99，则返回1.对于100-999，则返回2，依此类推.
整数指数
上述算法的相反之处是微不足道的:要计算10的整数次幂，我们只需要将幂左移几位即可.
integerExponent(count):值= shl(1，计数)返回值 因此，对于0，它将返回1；对于0，将返回1.为1，则返回10；对于2，返回100；对于3，返回1000；等等.
分解整数和分数
现在，我们可以处理整数幂和对数，几乎可以处理小数部分了.但是，在我们真正谈论如何计算对数的小数部分之前，我们必须谈论如何对问题进行除法，以便我们可以将整数部分与小数部分分开计算.理想情况下，我们只想处理固定范围内数字的对数-例如，从1到10，而不是从1到无穷大.
我们可以使用我们的整数对数和指数例程对完整的对数问题进行切分，以便无论输入数字是多少，我们总是在处理[1，10)范围内的值.
首先，我们计算整数对数，然后计算整数指数，然后从原始数中减去该对数.剩下的就是我们需要计算的小数部分:然后剩下的唯一工作就是移动该小数部分，以使其始终处于一致的范围内.
normalize(value):intLog = integerLogarithm(value)//从0到12(有意义的数字)如果intLog< = 5，则小于值= shr(值，intLog-5)转到完成少于:值= shl(值，5-intLog)完毕:返回值 您可以花费很少的精力说服自己，无论原始值是多少，其最高非零数字都将移至第7列:因此，"12345"将变为"000000123450"(即"0000001.23450").这使我们能够假装总是存在一个不可见的小数点，该数字比数字的一半还少一点，因此现在我们只需要解决计算[1，10)范围内的对数的问题.
(为什么超过一半"?我们将需要值的上半部分始终为零，一会儿您就会明白为什么.)
分数对数
Knuth在计算机编程的艺术第1.2.2节中说明了如何执行此操作.我们的目标是计算log10(x)，以便对于 b1 ， b2 ， b3 ...的某些值，其中n 已经是 0 (因为我们分割了上面的整数部分):
log10(x)= n + b1/2 + b2/4 + b3/8 + b4/16 + ...
Knuth说我们可以这样获得 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;b [k] = 1，如果x [k-1] ^ 2> = 10，则x [k] = x [k-1] ^ 2/10.
也就是说，每个步骤都使用伪代码循环，如下所示:
fractionalLogarithm(x):对于i = 1到numberOfBinaryDigitsOfPrecision:nextX = x * x如果nextX<然后10:b [i] = 0别的:b [i] = 1nextX = nextX/10 为了使用上面的定点数实现此目的，我们必须使用移位将小数点移回原位的方式来实现 x * x .正如Knuth所说，这将导致错误传播，但是它将提供足够的准确性，足以用于演示目的.
因此，给定由 normalize(value)生成的分数值，我们可以像这样计算其分数二进制对数:
fractionalLogarithm(value):对于i = 1到20:值= shr(值*值，6)如果值＜1000000然后:b [i] = 0别的:b [i] = 1值= shr(值，1) 但是 binary 分数对数-单个位！—并不是特别有用，特别是因为我们在前面的步骤中计算了对数整数部分的十进制版本.因此，我们将再次修改此时间，以计算一个 decimal 分数对数到5个位，而不是计算一个位数组.为此，我们需要一个由20个值组成的表格，这些表格代表每个这些位到十进制的转换，并且还将它们存储为定点数:
表[1] = 1/(2 ^ 1)= 1/2 = 500000表格[2] = 1/(2 ^ 2)= 1/4 = 250000table [3] = 1/(2 ^ 3)= 1/8 = 125000表格[4] = 1/(2 ^ 4)= 1/16 = 062500表格[5] = 1/(2 ^ 5)= 1/32 = 031250table [6] = 1/(2 ^ 6)= 1/64 = 015625...表格[17] = 1/(2 ^ 17)= 1/131072 = 000008表格[18] = 1/(2 ^ 18)= 1/262144 = 000004表格[19] = 1/(2 ^ 19)= 1/514288 = 000002表格[20] = 1/(2 ^ 20)= 1/1048576 = 000001 因此，现在有了该表，我们可以使用纯整数数学生成整个分数对数:
fractionalLogarithm(value):对数= 0对于i = 1到20:值= shr(值*值，6)如果值> = 1000000，则:日志=日志+表格[i]值= shr(值，1)返回日志 全部组合
最后，对于您的机器可以代表的任何整数的完整对数，这就是全部，它将以六位数的精度计算对数，形式为"0000XX.XXXXXX":
log(value):intPart = integerLogarithm(值)值=归一化(值)fracPart =分数对数(值)结果= shl(intPart，6)+ fracPart返回结果 演示
证明数学有效，并且效果很好！—以下是上述算法的JavaScript实现.它使用纯整数数学:仅加法，减法和相对比较.函数用于组织代码，但是它们的行为类似于子例程:它们不是递归的，并且嵌套的也不深.
您可以现场试用(单击运行"按钮，然后在输入字段中键入 12345 ).将结果与标准的 Math.log()函数进行比较，您将看到纯整数版本的接近程度:
function shiftLeft(value){var value2 =值+值；var value4 = value2 + value2;var value5 = value4 + value;返回value5 + value5;}函数shl(value，count){一会儿(计数> 0){值= shiftLeft(值);计数=计数-1;}返回值；}函数shr(value，count){if(count == 0)返回值；var index = 11;var shifted = 0;而(索引> = 0){var adder = shl(1，index-count);var减法器= shl(加法器，计数);while(值>减法器){值=值-减法器;移位=移位+加法器;}索引=索引-1;}回报转移；}//-----------------------------------函数multiByTwo(value){返回值+值；}函数multiByPowerOfTwo(value，count){一会儿(计数> 0){值=值+值;计数=计数-1;}返回值；}函数splitByPowerOfTwo(value，count){if(count == 0)返回值；var index = 39;//lg(floor(pow(10，12)))var shifted = 0;而(索引> = 0){var adder = multipleByPowerOfTwo(1，index-count);var减法器= multipleByPowerOfTwo(加法器，计数);while(值> =减法器){值=值-减法器;移位=移位+加法器;}索引=索引-1;}回报转移；}函数divideByTwo(值){返回dividerByPowerOfTwo(value，1);}函数乘法(a，b){var product = 0;而(b> 0){nextB = dividByTwo(b);位= b-multipliByTwo(nextB);如果(位！= 0){乘积+ = a;}a = a + a;b = nextB;}退货；}//-----------------------------------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};//-----------------------------------函数integerLogarithm(value){var count = 0;一会儿(值> 9){值= shr(值，1);计数=计数+ 1;}返回计数；}函数normalize(value){var intLog = integerLogarithm(value);如果(intLog> 5)值= shr(值，intLog-5);别的值= shl(值，5-intLog);返回值；}函数fractalLogarithm(值){var log = 0;对于(i = 1; i< 20; i ++){var squaredValue =乘法(值，值);值= shr(squaredValue，5);如果(值> = 1000000){log =日志+ logTable [i];值= shr(值，1);}}返回日志；}函数log(value){var intPart = integerLogarithm(value);值= normalize(值);var fracPart = fractionalLogarithm(value);var结果= shl(intPart，6)+ fracPart;返回结果；}//-----------------------------------//只需执行一些jQuery事件处理即可将UI封装在上述函数周围.$(#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 type ="text" id ="InputValue"/>< br/>< br/>使用整数算法的结果:< span id ="OutputValue"></span>< br/>< br/>真实对数:< span id ="TrueResult"></span>< br/> I am restoring the Ascota 170 antique mechanical programmable computer. It is already working. Now I’m looking for an algorithm to demonstrate its capabilities — like calculating trigonometric or logarithmic tables. Or something like that. Unfortunately, from mathematical operations, a computer is only capable of adding and subtracting integers (55 registers from -1E12 to 1E12). There is not even a shift-to-digit operation — so that it can be programmatically implemented to multiply only by very small numbers. But its logical operations are very well developed.
Could you advise me any suitable algorithm?
So what you're doing is really kinda awesome. And as it happens, I can explain quite a bit about how to implement fractional logarithms using only integer addition and subtraction! This post is going to be long, but there's lots of detail included, and a working implementation at the end, and it should be enough for you to do some fun things with your weird mechanical computer.
Implementing Comparisons
You're going to need to be able to compare numbers. While you said you can perform comparisons == 0 and > 0, that's not really quite enough for most of the interesting algorithms you'll want to implement. You need relative comparisons, which can be determined via subtraction:
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
For the rest of this post, I'm just going to write the simpler form of a > b, but if you can't do that directly, you can substitute in one of the operations above.
Implementing Shifts
Now, since you don't have digit-shifting hardware, you'll have to create "routines" to implement it. A left-shift is easy: Add a number to itself, and again, and again, and then add the original number, and then add it one more time; and that's the equivalent of shifting left by 1 digit.
So shift left by one digit, or multiply-by-ten:
shiftLeft(value):
value2 = value + value
value4 = value2 + value2
value5 = value4 + value
return value5 + value5
Shifting by many digits is just repeated invocation of shiftLeft():
shl(value, count):
repeat:
if count <= 0 then goto done
value = shiftLeft(value)
count = count - 1
done:
return value
Shifting right by one digit is a little harder: We need to do this with repeated subtraction and addition, as in the pseudocode below:
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
Conveniently, since it's hard to shift right in the first place, the algorithm lets us directly choose how many digits to shift by.
Multiplication
It looks like your hardware might have multiplication? But if it doesn't, you can implement multiplication using repeated addition and shifting. Binary multiplication is the easiest form to implement that's actually efficient, and that requires us to first implement multiplyByTwo() and divideByTwo(), using the same basic techniques that we used to implement shiftLeft() and shr().
Once you have those implemented, multiplication involves repeatedly slicing off the last bit of one of the numbers, and if that bit is a 1, then adding a growing version of the other number to the running total:
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
A full implementation of this is included below, if you need it.
Integer Logarithms
We can use our ability to shift right by a digit to calculate the integer part of the base-10 logarithm of a number — this is really just how many times you can shift the number right before you reach a number too small to shift.
integerLogarithm(value):
count = 0
repeat:
if value <= 9 then goto done
value = shiftRight(value)
count = count + 1
goto repeat
done:
return count
So for 0-9, this returns 0; for 10-99, this returns 1; for 100-999 this returns 2, and so on.
Integer Exponents
The opposite of the above algorithm is pretty trivial: To calculate 10 raised to an integer power, we just shift the digits left by the power.
integerExponent(count):
value = shl(1, count)
return value
So for 0, this returns 1; for 1, this return 10; for 2, this returns 100; for 3, this returns 1000; and so on.
Splitting the Integer and Fraction
Now that we can handle integer powers and logarithms, we're almost ready to handle the fractional part. But before we can really talk about how to compute the fractional part of the logarithm, we have to talk about how to divide up the problem so we can compute the fractional part separately from the integer part. Ideally, we only want to deal with computing logarithms for numbers in a fixed range — say, from 1 to 10, rather than from 1 to infinity.
We can use our integer logarithm and exponent routines to slice up the full logarithm problem so that we're always dealing with a value in the range of [1, 10), no matter what the input number was.
First, we calculate the integer logarithm, and then the integer exponent, and then we subtract that from the original number. Whatever is left over is the fractional part that we need to calculate: And then the only remaining exercise is to shift that fractional part so that it's always in a consistent range.
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
You can convince yourself with relatively little effort that no matter what the original value was, its highest nonzero digit will be moved to column 7: So "12345" will become "000000123450" (i.e., "0000001.23450"). This allows us to pretend that there's always an invisible decimal point a little more than halfway down the number, so that now we only need to solve the problem of calculating logarithms of values in the range of [1, 10).
(Why "more than halfway"? We will need the upper half of the value to always be zero, and you'll see why in a moment.)
Fractional Logarithms
Knuth explains how to do this in The Art of Computer Programming, section 1.2.2. Our goal will be to calculate log10(x) so that for some values of b1, b2, b3 ... , where n is already 0 (because we split out the integer portion above):
log10(x) = n + b1/2 + b2/4 + b3/8 + b4/16 + ...
Knuth says that we can obtain b1, b2, b3 ... like this:
To obtain b1, b2, ..., we now set x0 = x / 10^n and, for k >= 1,
b[k] = 0, x[k] = x[k-1] ^ 2, if x[k-1] ^ 2 < 10;
b[k] = 1, x[k] = x[k-1] ^ 2 / 10, if x[k-1] ^ 2 >= 10.
That is to say, each step uses pseudocode loop something like this:
fractionalLogarithm(x):
for i = 1 to numberOfBinaryDigitsOfPrecision:
nextX = x * x
if nextX < 10 then:
b[i] = 0
else:
b[i] = 1
nextX = nextX / 10
In order for this to work using the fixed-point numbers we have above, we have to implement x * x using a shift to move the decimal point back into place, which will lose some digits. This will cause error to propagate, as Knuth says, but it will give enough accuracy that it's good enough for demonstration purposes.
So given a fractional value generated by normalize(value), we can compute its fractional binary logarithm like this:
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)
But a binary fractional logarithm — individual bits! — isn't especially useful, especially since we computed an decimal version of the integer part of the logarithm in the earlier step. So we'll modify this one more time, to calculate a decimal fractional logarithm, to five places, instead of calculating an array of bits; for that, we'll need a table of 20 values that represent the conversions of each of those bits to decimal, and we'll store them as fixed-point as well:
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
So now with that table, we can produce the whole fractional logarithm, using pure integer math:
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
Putting It All Together
Finally, for a complete logarithm of any integer your machine can represent, this is the whole thing, which will compute the logarithm with six digits of precision, in the form "0000XX.XXXXXX":
log(value):
intPart = integerLogarithm(value)
value = normalize(value)
fracPart = fractionalLogarithm(value)
result = shl(intPart, 6) + fracPart
return result
Demonstration
To show that the math works — and that it works pretty well! — below is a JavaScript implementation of the above algorithm. It uses pure integer math: Only addition, subtraction, and relative comparison. Functions are used to organize the code, but they behave like subroutines: They're not recursive, and don't nest very deeply.
You can try it out live (click the 'Run' button and type 12345 in the input field). Compare the result to the standard Math.log() function, and you'll see how close the pure-integer version gets:
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 />
这篇关于用于计算三角函数，对数或类似内容的算法.仅加减的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
