Почему моя программа возвращает Nan для некоторых значений, а не для других?
В 4-м издании «Алгоритмов» (Седжвик) есть вопрос, который я пытался задать:
У меня ограниченные познания в математике и отсутствие практики. Я использовал эту ветку, так как мне было трудно найти уравнение для вычисления логарифмов (мои плохие навыки поиска), и на данный момент я реализовал программу:
public class HelloWorld {
static final int TAYLOR_ITERS = 20;
public static void main(String[] args) {
System.out.println(HelloWorld.lg(3));
System.out.println(Math.log(3));
}
public static double lg(int n) {
double answer = 0;
for (int i = 1; i < TAYLOR_ITERS; i++) {
double temp = (n - 1);
int power = i;
while (power != 1) {
temp *= (n - 1);
power--;
}
if (i % 2 == 0) {
answer -= ((temp) / i);
}
else {
answer += ((temp) / i);
}
}
return answer;
}
public static double exercise(int n) {
double answer = HelloWorld.lg(n) / HelloWorld.lg(2);
return answer;
}
}
Во-первых, я прошу прощения за неправильную структуру/условия кода, я впервые использую Java после использования C и в основном Python. Без функции мощности я использовал цикл for для получения значения temp отдельно i-1 раз, например, когда i==2 temp*temp = temp^2, а power then = 1, и цикл не будет продолжаться. Затем я использую мод 2, чтобы проверить, является ли я нечетным или четным, поскольку я думаю, что ряд, представленный в ссылке выше, чередует вычитание и сложение для четных/нечетных итераций.
Очевидно, что между тем, что возвращает Math.log(), и моей собственной функцией журнала есть большие различия, но я не могу четко понять, что происходит не так.
Ах, и это потому, что n — это произведение основания (2), возведенное в степень некоторой степени, верно?
@AngusHay отладьте ваше приложение. Единственный способ получить NaN (концепция double/float): [1] любая операция, которая сама включает NaN. Например, 5/NaN — это NaN, [2] деление 0,0 на 0,0. [3] Множество взаимодействий с бесконечностью, например infinity - infinity, infinity / infinity и так далее. Пройдитесь по коду шаг за шагом, чтобы найти ответ. В любое время, когда первой появляется бесконечность или NaN? Это место.
Либо используйте отладчик, либо добавьте трассировки для соответствующих переменных. (Обучение отладке является частью обучения программированию.)
В упражнении сказано, что ваш метод должен возвращать int, но объявлено, что ваш метод возвращает double?
Привет, да, я подумал, что мне следует сократить до int, но, как отметили другие пользователи, я совершенно неправильно понял вопрос.
Ответы 2
На самом деле, я не могу интерпретировать логику вашего кода (возможно, я немного туповат), поэтому предлагаю другой способ достижения результата:
public double lg( int n ) {
// we determine the accuracy
int decimalsAmount = 10;
// value of the increase
double adicion = 1,
answer = 1;
for( int i = 0; i < decimalsAmount; answer += increase ) {
// we obtain the result of applying our proposal
double aux = pow( 2, answer );
// if the result is greater than the target, we subtract from **answer**,
// the value of **increase** previously applied, divide **increase**
// by "10", and increase **i** by "1".
if ( aux > n ) {
answer -= increase;
increase /= 10;
i++;
}
}
return answer;
}
Во-первых, причина, по которой ваш код не работает, заключается в том, что ряд Тейлора для lg работает только для значений в диапазоне от 0 до 2; выше 2 - это почти все случаи, которые вам нужны - он быстро расходится, быстро создавая числа, большие, чем могут быть обработаны в системе с плавающей запятой, которую использует Java. Вы можете исправить(?) это, вместо этого вычислив журнал обратной величины и отрицая его, но даже там для значений, не близких к единице, он сходится очень медленно, занимая гораздо больше, чем разрешенные вами 20 итераций.
Но дело в том, что вы неправильно прочитали задание. Он не запрашивает фактическую базу журнала-2; он запрашивает наибольшее целое число, не превышающее log-base-2. Это совсем другое дело; это просто позиция старшего бита в двоичном представлении n, и поскольку Java (как и все компьютеры за последние шесть десятилетий) использует двоичные целые числа, это тривиально; как прокомментировал Гай, просто разделите на 2 (или, что то же самое, сдвиньте вправо на 1), пока вы не «израсходуете» все биты ниже того, который начался с самого высокого. Или немного менее очевидно, но еще более эффективно: вы можете выполнить двоичный поиск старшего бита.
Следующий код иллюстрирует оба (все) метода и в процессе показывает, сколько итераций Тейлора необходимо, чтобы получить хотя бы приличное приближение, которое все еще не совсем корректно для больших значений и его нужно будет подделать.
public class SO78863494ilog2 {
public static double abs (double x) { return x<0? -x: x; }
public static double lg_taylor (double x) {
if ( x <= 0 || x > 2 ) throw new RuntimeException("invalid for lg_taylor");
double t=0, p=1; track=0;
for(int i = 1; abs(p *= x-1)/i>1e-9; i++){ t = i%2==0? t-p/i: t+p/i; track++; }
// or t += (i%2==0?-1:+1)*p/i or more clever/sneaky (i%2*2-1)*p/i
return t;
}
public static int track;
public static double lg_2 = -lg_taylor(1.0/2);
public static double log2 (int n){ return -lg_taylor(1.0/n)/lg_2; }
public static int ilog2 (int n){
if ( n <= 0 ) throw new RuntimeException("invalid for ilog2");
int l=0; while(n>1){ n/=2; l++; } // or n>>=1;
return l;
}
public static int ilog2opt (int n){
if ( n <= 0 ) throw new RuntimeException("invalid for ilog2");
int l=0, t;
if ( (t=n>>16)>0 ){ n=t; l+=16; }
if ( (t=n>>8) >0 ){ n=t; l+=8; }
if ( (t=n>>4) >0 ){ n=t; l+=4; }
if ( (t=n>>2) >0 ){ n=t; l+=2; }
if ( (t=n>>1) >0 ){ n=t; l+=1; }
return l;
}
public static void main(String[] args){
int[] data = {3,4,15,16,63,64,255,256,1023,1024,4095,4096,16383,16384};
for(int t : data) System.out.printf ("%5d: %f(%d) %d %d%n", t, log2(t), track, ilog2(t), ilog2opt(t));
}
}
-->
3: 1.584962(41) 1 1
4: 2.000000(57) 2 2
15: 3.906891(222) 3 3
16: 4.000000(236) 4 4
63: 5.977280(872) 5 5
64: 6.000000(885) 6 6
255: 7.994353(3218) 7 7
256: 8.000000(3230) 8 8
1023: 9.998589(11618) 9 9
1024: 9.999999(11629) 10 10
4095: 11.999642(41329) 11 11
4096: 11.999995(41338) 12 12
16383: 13.999891(144821) 13 13
16384: 13.999979(144829) 14 14
Спасибо за код и объяснение, теперь я помню, что ряд Тейлора работает для многих общих функций, но я забыл, что для n > 2 он циклически повторяется для ln. Однако я немного недоволен тем, что не понял, о чем идет речь, и до сих пор не могу понять, откуда я должен был это сделать. Возможно, я могу понять, что log_2(N) = x, 2^x = N, и тогда вы можете разделить на 2 x количество раз... (я думаю?), но я не понимаю самый высокий бит, который вы упомянули, как это сделать эти два коррелируют? Я хотел бы знать, как понимать подобные вопросы в будущем.
Подождите, я думаю, я понимаю, почему, возможно, я провел слишком много времени вдали от двоичного представления, чтобы вспомнить, что числа являются двоичными! Если в вопросе задается основание 2, то он, вероятно, будет содержать двоичные числа из-за положения битов… верно? 3210 -> показатель степени 2, позиция бита 1001, поэтому (2^3 * 1) + (2^0 * 1) = 9, поэтому, если N = 9, то наибольшее целое число равно 8?
@AngusHay, это основано на разложении числа: N = b(0) * 2^0 + b(1) * 2^1 + ... + b(n - 1) * 2^(n - 1).
На самом деле это не ответ на точный вопрос, но вы сильно усложняете упражнение. Ответ можно получить, многократно разделив число на 2 (целое деление), пока не достигнет 1. Ответом является количество выполненных делений.