Это потому, что
res = [[None] * len(A) for _ in range(len(A[0]))]
создает список, содержащий len (A [0]) разных списков, тогда как
res = [[None] * len(A)] * len(A[0]) # why this doesn't work
создает список, содержащий len (A [0]) ссылки на один и тот же список, так что изменение значения в одном из них изменяет его во всех.
См. Список изменений списков, неожиданно отразившихся в подсписках среди других ...
Java Number Cruncher: Руководство программиста Java по численным вычислениям предоставляет решение с использованием метода Ньютона . Исходный код из книги доступен здесь . Следующее было взято из главы 12.5 Большие десятичные функции (p330 и p331):
/**
* Compute the natural logarithm of x to a given scale, x > 0.
*/
public static BigDecimal ln(BigDecimal x, int scale)
{
// Check that x > 0.
if (x.signum() <= 0) {
throw new IllegalArgumentException("x <= 0");
}
// The number of digits to the left of the decimal point.
int magnitude = x.toString().length() - x.scale() - 1;
if (magnitude < 3) {
return lnNewton(x, scale);
}
// Compute magnitude*ln(x^(1/magnitude)).
else {
// x^(1/magnitude)
BigDecimal root = intRoot(x, magnitude, scale);
// ln(x^(1/magnitude))
BigDecimal lnRoot = lnNewton(root, scale);
// magnitude*ln(x^(1/magnitude))
return BigDecimal.valueOf(magnitude).multiply(lnRoot)
.setScale(scale, BigDecimal.ROUND_HALF_EVEN);
}
}
/**
* Compute the natural logarithm of x to a given scale, x > 0.
* Use Newton's algorithm.
*/
private static BigDecimal lnNewton(BigDecimal x, int scale)
{
int sp1 = scale + 1;
BigDecimal n = x;
BigDecimal term;
// Convergence tolerance = 5*(10^-(scale+1))
BigDecimal tolerance = BigDecimal.valueOf(5)
.movePointLeft(sp1);
// Loop until the approximations converge
// (two successive approximations are within the tolerance).
do {
// e^x
BigDecimal eToX = exp(x, sp1);
// (e^x - n)/e^x
term = eToX.subtract(n)
.divide(eToX, sp1, BigDecimal.ROUND_DOWN);
// x - (e^x - n)/e^x
x = x.subtract(term);
Thread.yield();
} while (term.compareTo(tolerance) > 0);
return x.setScale(scale, BigDecimal.ROUND_HALF_EVEN);
}
/**
* Compute the integral root of x to a given scale, x >= 0.
* Use Newton's algorithm.
* @param x the value of x
* @param index the integral root value
* @param scale the desired scale of the result
* @return the result value
*/
public static BigDecimal intRoot(BigDecimal x, long index,
int scale)
{
// Check that x >= 0.
if (x.signum() < 0) {
throw new IllegalArgumentException("x < 0");
}
int sp1 = scale + 1;
BigDecimal n = x;
BigDecimal i = BigDecimal.valueOf(index);
BigDecimal im1 = BigDecimal.valueOf(index-1);
BigDecimal tolerance = BigDecimal.valueOf(5)
.movePointLeft(sp1);
BigDecimal xPrev;
// The initial approximation is x/index.
x = x.divide(i, scale, BigDecimal.ROUND_HALF_EVEN);
// Loop until the approximations converge
// (two successive approximations are equal after rounding).
do {
// x^(index-1)
BigDecimal xToIm1 = intPower(x, index-1, sp1);
// x^index
BigDecimal xToI =
x.multiply(xToIm1)
.setScale(sp1, BigDecimal.ROUND_HALF_EVEN);
// n + (index-1)*(x^index)
BigDecimal numerator =
n.add(im1.multiply(xToI))
.setScale(sp1, BigDecimal.ROUND_HALF_EVEN);
// (index*(x^(index-1))
BigDecimal denominator =
i.multiply(xToIm1)
.setScale(sp1, BigDecimal.ROUND_HALF_EVEN);
// x = (n + (index-1)*(x^index)) / (index*(x^(index-1)))
xPrev = x;
x = numerator
.divide(denominator, sp1, BigDecimal.ROUND_DOWN);
Thread.yield();
} while (x.subtract(xPrev).abs().compareTo(tolerance) > 0);
return x;
}
/**
* Compute e^x to a given scale.
* Break x into its whole and fraction parts and
* compute (e^(1 + fraction/whole))^whole using Taylor's formula.
* @param x the value of x
* @param scale the desired scale of the result
* @return the result value
*/
public static BigDecimal exp(BigDecimal x, int scale)
{
// e^0 = 1
if (x.signum() == 0) {
return BigDecimal.valueOf(1);
}
// If x is negative, return 1/(e^-x).
else if (x.signum() == -1) {
return BigDecimal.valueOf(1)
.divide(exp(x.negate(), scale), scale,
BigDecimal.ROUND_HALF_EVEN);
}
// Compute the whole part of x.
BigDecimal xWhole = x.setScale(0, BigDecimal.ROUND_DOWN);
// If there isn't a whole part, compute and return e^x.
if (xWhole.signum() == 0) return expTaylor(x, scale);
// Compute the fraction part of x.
BigDecimal xFraction = x.subtract(xWhole);
// z = 1 + fraction/whole
BigDecimal z = BigDecimal.valueOf(1)
.add(xFraction.divide(
xWhole, scale,
BigDecimal.ROUND_HALF_EVEN));
// t = e^z
BigDecimal t = expTaylor(z, scale);
BigDecimal maxLong = BigDecimal.valueOf(Long.MAX_VALUE);
BigDecimal result = BigDecimal.valueOf(1);
// Compute and return t^whole using intPower().
// If whole > Long.MAX_VALUE, then first compute products
// of e^Long.MAX_VALUE.
while (xWhole.compareTo(maxLong) >= 0) {
result = result.multiply(
intPower(t, Long.MAX_VALUE, scale))
.setScale(scale, BigDecimal.ROUND_HALF_EVEN);
xWhole = xWhole.subtract(maxLong);
Thread.yield();
}
return result.multiply(intPower(t, xWhole.longValue(), scale))
.setScale(scale, BigDecimal.ROUND_HALF_EVEN);
}
Вот что я придумал:
//http://everything2.com/index.pl?node_id=946812
public BigDecimal log10(BigDecimal b, int dp)
{
final int NUM_OF_DIGITS = dp+2; // need to add one to get the right number of dp
// and then add one again to get the next number
// so I can round it correctly.
MathContext mc = new MathContext(NUM_OF_DIGITS, RoundingMode.HALF_EVEN);
//special conditions:
// log(-x) -> exception
// log(1) == 0 exactly;
// log of a number lessthan one = -log(1/x)
if(b.signum() <= 0)
throw new ArithmeticException("log of a negative number! (or zero)");
else if(b.compareTo(BigDecimal.ONE) == 0)
return BigDecimal.ZERO;
else if(b.compareTo(BigDecimal.ONE) < 0)
return (log10((BigDecimal.ONE).divide(b,mc),dp)).negate();
StringBuffer sb = new StringBuffer();
//number of digits on the left of the decimal point
int leftDigits = b.precision() - b.scale();
//so, the first digits of the log10 are:
sb.append(leftDigits - 1).append(".");
//this is the algorithm outlined in the webpage
int n = 0;
while(n < NUM_OF_DIGITS)
{
b = (b.movePointLeft(leftDigits - 1)).pow(10, mc);
leftDigits = b.precision() - b.scale();
sb.append(leftDigits - 1);
n++;
}
BigDecimal ans = new BigDecimal(sb.toString());
//Round the number to the correct number of decimal places.
ans = ans.round(new MathContext(ans.precision() - ans.scale() + dp, RoundingMode.HALF_EVEN));
return ans;
}
Хакерский маленький алгоритм, который отлично работает для больших чисел, использует соотношение log (AB) = log (A ) + log (B)
. Вот как это сделать в базе 10 (которую вы можете легко преобразовать в любую другую базу логарифмов):
Подсчитайте количество десятичных цифр в ответе. Это неотъемлемая часть вашего логарифма, плюс один . Пример: floor (log10 (123456)) + 1
равно 6, поскольку 123456 имеет 6 цифр.
Вы можете остановиться здесь, если все, что вам нужно, это целая часть логарифма: просто вычтите 1 из результат шага 1.
Чтобы получить дробную часть логарифма, разделите число на 10 ^ (количество цифр)
, затем вычислите логарифм этого числа, используя math.log10 ()
(или что-то еще; используйте простое приближение рядов, если больше ничего не доступно), и добавьте его к целочисленной части. Пример: чтобы получить дробную часть log10 (123456)
, вычислите math.log10 (0.123456) = -0,908 ...
и добавьте его к результату шага 1: 6 + -0,908 = 5,092
, что составляет log10 (123456)
. Обратите внимание, что вы в основном просто добавляете десятичную точку к началу большого числа; вероятно, есть хороший способ оптимизировать это в вашем случае использования, и для действительно больших чисел вам даже не нужно беспокоиться о захвате всех цифр - log10 (0.123)
является хорошим приближением к log10 (0.123456789)
.
Вы можете разложить его, используя
log(a * 10^b) = log(a) + b * log(10)
В основном b + 1
будет количеством цифр в числе,
Я написал запись блога некоторое время назад, чтобы проиллюстрировать очень простой плагин системы. Это может быть достаточно хорошо для ваших потребностей:
http://crazorsharp.blogspot.com/2009/03/net-reflection-part-2-loading.html
-121--4690988-Если вы не используете какой-то уровень абстракции базы данных, просто позвоните mysql _ real _ побег _ последовательность на текст.
-121--4648532-Алгоритм псевдокода для выполнения логарифма.
Предполагая, что мы хотим log_n x
double fraction, input;
int base;
double result;
result = 0;
base = n;
input = x;
while (input > base){
result++;
input /= base;
}
fraction = 1/2;
input *= input;
while (((result + fraction) > result) && (input > 1)){
if (input > base){
input /= base;
result += fraction;
}
input *= input;
fraction /= 2.0;
}
Большой цикл while может показаться немного запутанным.
При каждом проходе можно либо выполнить квадрат ввода, либо получить квадратный корень основания; в любом случае, вы должны разделить свою долю на 2. Я нахожу возведение в квадрат входных данных и оставление базы в покое, чтобы быть более точным.
Если входной сигнал принимает значение 1, мы пройдем. Журнал 1 для любой базы равен 0, что означает, что нам больше не нужно добавлять.
Если (результат + дробь) не больше результата, то мы достигли пределов точности для нашей системы нумерации. Мы можем остановиться.
Очевидно, что если вы работаете с системой, которая имеет произвольно много цифр точности, вы захотите поместить там что-то еще, чтобы ограничить цикл.