Я написал вариант Ryu (в частности, этот алгоритм преобразования двойной строки) для своего варианта использования:
сделал его двойным для выходного потока (поэтому мне не нужно вызывать String.getBytes(), избавляя меня от использования String-подобного и промежуточного буфера)
удалил соответствие Double.toString, но сохранил совместимость Double.parseDouble. Это делается для того, чтобы гарантировать, что то, что я пишу в свой выходной поток, действительно может быть легко прочитано без получения другого двойного значения (на самом деле я также проверил, что библиотека Джексона может прочитать это обратно, и это работает, я думаю).
удалена обработка конечных нулей (я согласен напечатать еще несколько цифр вместо добавления более непредсказуемых if)
предположил RoundingMode для всегда быть ROUND_EVEN
удалены журналы отладки
поддерживается только научная нотация (за исключением случаев, когда показатель степени равен 0 и, конечно, для NaN и +/- бесконечности)
добавлен локальный рабочий буфер потока
поместите Ключевое слово Final здесь и там
изменило точку входа в функцию. В исходном коде была public static String doubleToString(double value), в моем это public static void doubleToStream(final double value, Final OutputStream out)
моя функция обрабатывает базовые случаи (0, Infinity и NaN) перед вызовом Private static int fillBuffer(final long bits, Final byte[] result), что похоже на начало исходного алгоритма Ryu с этого линия. Эта функция похожа на исходную функцию String doubleToString(double value, RoundingMode roundingMode), но вместо возврата строки она заполняет массив байтов, переданный в качестве параметра, и возвращает количество записанных байтов.
import java.io.IOException;
import java.io.OutputStream;
import java.math.BigInteger;
public final class RyuDoubleIsh {
private RyuDoubleIsh() {
}
private static final int DOUBLE_MANTISSA_BITS = 52;
private static final long DOUBLE_MANTISSA_MASK = (1L > DOUBLE_MANTISSA_BITS) & DOUBLE_EXPONENT_MASK);
final long ieeeMantissa = bits & DOUBLE_MANTISSA_MASK;
final int e2;
final long m2;
if (ieeeExponent == 0) {
// Denormal number - no implicit leading 1, and the exponent is 1, not 0.
e2 = 1 - DOUBLE_EXPONENT_BIAS - DOUBLE_MANTISSA_BITS - 2;
m2 = ieeeMantissa;
} else {
// Add implicit leading 1.
e2 = ieeeExponent - DOUBLE_EXPONENT_BIAS - DOUBLE_MANTISSA_BITS - 2;
m2 = ieeeMantissa | (1L >> 20) - 1);
final int i = -e2 - q;
final int k = pow5bits(i) - POW5_BITCOUNT;
final int j = q - k;
dv = mulPow5divPow2(mv, i, j);
dp = mulPow5divPow2(mp, i, j);
dm = mulPow5divPow2(mm, i, j);
e10 = q + e2;
if (q dm / 10) {
lastRemovedDigit = (int) (dv % 10);
dp /= 10;
dv /= 10;
dm /= 10;
removed++;
}
output = dv + ((dv == dm || (lastRemovedDigit >= 5)) ? 1 : 0);
final int olength = vplength - removed;
// Step 5: Print the scientific notation
int index = 0;
if (sign) {
result[index++] = '-';
}
// Print in the format x.xxxxxE-yy.
for (int i = 0; i < olength - 1; i++) {
int c = (int) (output % 10);
output /= 10;
result[index + olength - i] = (byte) ('0' + c);
}
result[index] = (byte) ('0' + output % 10);
result[index + 1] = '.';
index += olength + 1;
if (olength == 1) {
result[index++] = '0';
}
// Print 'E', the exponent sign, and the exponent, which has at most three digits.
if (exp != 0) {
result[index++] = 'E';
if (exp < 0) {
result[index++] = '-';
exp = -exp;
}
if (exp >= 100) {
result[index++] = (byte) ('0' + exp / 100);
exp %= 100;
result[index++] = (byte) ('0' + exp / 10);
} else if (exp >= 10) {
result[index++] = (byte) ('0' + exp / 10);
}
result[index++] = (byte) ('0' + exp % 10);
}
return index;
}
private static int pow5bits(final int e) {
return ((e * 1217359) >>> 19) + 1;
}
// JIT somehow optimize this, and it's faster than performing log magic
private static int decimalLength(final long v) {
if (v >= 1000000000000000000L) return 19;
if (v >= 100000000000000000L) return 18;
if (v >= 10000000000000000L) return 17;
if (v >= 1000000000000000L) return 16;
if (v >= 100000000000000L) return 15;
if (v >= 10000000000000L) return 14;
if (v >= 1000000000000L) return 13;
if (v >= 100000000000L) return 12;
if (v >= 10000000000L) return 11;
if (v >= 1000000000L) return 10;
if (v >= 100000000L) return 9;
if (v >= 10000000L) return 8;
if (v >= 1000000L) return 7;
if (v >= 100000L) return 6;
if (v >= 10000L) return 5;
if (v >= 1000L) return 4;
if (v >= 100L) return 3;
if (v >= 10L) return 2;
return 1;
}
private static int pow5Factor(long value) {
// We want to find the largest power of 5 that divides value.
if ((value % 5) != 0) return 0;
if ((value % 25) != 0) return 1;
if ((value % 125) != 0) return 2;
if ((value % 625) != 0) return 3;
int count = 4;
value /= 625;
while (value > 0) {
if (value % 5 != 0) {
return count;
}
value /= 5;
count++;
}
throw new IllegalArgumentException("" + value);
}
/**
* Compute the high digits of m * 5^p / 10^q = m * 5^(p - q) / 2^q = m * 5^i / 2^j, with q chosen
* such that m * 5^i / 2^j has sufficiently many decimal digits to represent the original floating
* point number.
*/
private static long mulPow5divPow2(final long m, final int i, final int j) {
// m has at most 55 bits.
final long mHigh = m >>> 31;
final long mLow = m & 0x7fffffff;
final long bits13 = mHigh * POW5_SPLIT[i][0]; // 124
final long bits03 = mLow * POW5_SPLIT[i][0]; // 93
final long bits12 = mHigh * POW5_SPLIT[i][1]; // 93
final long bits02 = mLow * POW5_SPLIT[i][1]; // 62
final long bits11 = mHigh * POW5_SPLIT[i][2]; // 62
final long bits01 = mLow * POW5_SPLIT[i][2]; // 31
final long bits10 = mHigh * POW5_SPLIT[i][3]; // 31
final long bits00 = mLow * POW5_SPLIT[i][3]; // 0
final int actualShift = j - 3 * 31 - 21;
return ((((((
((bits00 >>> 31) + bits01 + bits10) >>> 31)
+ bits02 + bits11) >>> 31)
+ bits03 + bits12) >>> 21)
+ (bits13 >> actualShift;
}
/**
* Compute the high digits of m / 5^i / 2^j such that the result is accurate to at least 9
* decimal digits. i and j are already chosen appropriately.
*/
private static long mulPow5InvDivPow2(final long m, final int i, final int j) {
// m has at most 55 bits.
final long mHigh = m >>> 31;
final long mLow = m & 0x7fffffff;
final long bits13 = mHigh * POW5_INV_SPLIT[i][0];
final long bits03 = mLow * POW5_INV_SPLIT[i][0];
final long bits12 = mHigh * POW5_INV_SPLIT[i][1];
final long bits02 = mLow * POW5_INV_SPLIT[i][1];
final long bits11 = mHigh * POW5_INV_SPLIT[i][2];
final long bits01 = mLow * POW5_INV_SPLIT[i][2];
final long bits10 = mHigh * POW5_INV_SPLIT[i][3];
final long bits00 = mLow * POW5_INV_SPLIT[i][3];
final int actualShift = j - 3 * 31 - 21;
return ((((((
((bits00 >>> 31) + bits01 + bits10) >>> 31)
+ bits02 + bits11) >>> 31)
+ bits03 + bits12) >>> 21)
+ (bits13 >> actualShift;
}
}
У меня возникли серьезные проблемы с поиском параметра с двойным значением для doubleToStream
который будет охватывать последнюю строку функции int decimalLength(final long v) (в основном кажется, что его параметр dp в самом начале // шага 4 всегда >= 10)
(СМОТРИТЕ СЛЕДУЮЩИЙ ПАРАГРАФ, Я ДЕЙСТВИТЕЛЬНО РЕШИЛ ЭТОТ ПУНКТ), который заставит функцию int pow5Factor(long value) возвращать значение > 4 (функция вызывается здесь только в том случае, если (q = q) { и только с mp в качестве параметра). Кажется, что внутренний цикл выполнит не более 1 итерации.
Я попробовал вернуться к математике, но делаю что-то не так, потому что всегда получаю двойное значение, которое не охватывает эти случаи. Если это действительно так и эти линии не могут быть покрыты, алгоритм действительно можно улучшить. Пожалуйста, помогите мне найти эти странные случаи.
Обновление — пункт 2 выполнен — покрытие pow5Factor
В итоге я написал довольно умный цикл, который перебирает все возможные значения mp, которые будут переданы в pow5Factor. Я не позволил программе завершиться, но в итоге получил следующие значения мантиссы, охватывающие случаи от 1 до 18:
Я написал вариант Ryu (в частности, этот алгоритм преобразования двойной строки) для своего варианта использования: [list] [*]сделал его двойным для выходного потока (поэтому мне не нужно вызывать String.getBytes(), избавляя меня от использования String-подобного и промежуточного буфера)
[*]удалил соответствие Double.toString, но сохранил совместимость Double.parseDouble. Это делается для того, чтобы гарантировать, что то, что я пишу в свой выходной поток, действительно может быть легко прочитано без получения другого двойного значения (на самом деле я также проверил, что библиотека Джексона может прочитать это обратно, и это работает, я думаю).
[*]удалена обработка конечных нулей (я согласен напечатать еще несколько цифр вместо добавления более непредсказуемых if)
[*]предположил RoundingMode для всегда быть ROUND_EVEN
[*]удалены журналы отладки
[*]поддерживается только научная нотация (за исключением случаев, когда показатель степени равен 0 и, конечно, для NaN и +/- бесконечности)
[*]добавлен локальный рабочий буфер потока
[*]поместите Ключевое слово Final здесь и там
[*]изменило точку входа в функцию. В исходном коде была public static String doubleToString(double value), в моем это public static void doubleToStream(final double value, Final OutputStream out)
моя функция обрабатывает базовые случаи (0, Infinity и NaN) перед вызовом Private static int fillBuffer(final long bits, Final byte[] result), что похоже на начало исходного алгоритма Ryu с этого линия. Эта функция похожа на исходную функцию String doubleToString(double value, RoundingMode roundingMode), но вместо возврата строки она заполняет массив байтов, переданный в качестве параметра, и возвращает количество записанных байтов. [/list]
Вот код: [code] import java.io.IOException; import java.io.OutputStream; import java.math.BigInteger;
public final class RyuDoubleIsh {
private RyuDoubleIsh() { }
private static final int DOUBLE_MANTISSA_BITS = 52; private static final long DOUBLE_MANTISSA_MASK = (1L > DOUBLE_MANTISSA_BITS) & DOUBLE_EXPONENT_MASK); final long ieeeMantissa = bits & DOUBLE_MANTISSA_MASK; final int e2; final long m2; if (ieeeExponent == 0) { // Denormal number - no implicit leading 1, and the exponent is 1, not 0. e2 = 1 - DOUBLE_EXPONENT_BIAS - DOUBLE_MANTISSA_BITS - 2; m2 = ieeeMantissa; } else { // Add implicit leading 1. e2 = ieeeExponent - DOUBLE_EXPONENT_BIAS - DOUBLE_MANTISSA_BITS - 2; m2 = ieeeMantissa | (1L >> 20) - 1); final int i = -e2 - q; final int k = pow5bits(i) - POW5_BITCOUNT; final int j = q - k; dv = mulPow5divPow2(mv, i, j); dp = mulPow5divPow2(mp, i, j); dm = mulPow5divPow2(mm, i, j); e10 = q + e2; if (q dm / 10) { lastRemovedDigit = (int) (dv % 10); dp /= 10; dv /= 10; dm /= 10; removed++; } output = dv + ((dv == dm || (lastRemovedDigit >= 5)) ? 1 : 0); final int olength = vplength - removed; // Step 5: Print the scientific notation int index = 0; if (sign) { result[index++] = '-'; } // Print in the format x.xxxxxE-yy. for (int i = 0; i < olength - 1; i++) { int c = (int) (output % 10); output /= 10; result[index + olength - i] = (byte) ('0' + c); } result[index] = (byte) ('0' + output % 10); result[index + 1] = '.'; index += olength + 1; if (olength == 1) { result[index++] = '0'; } // Print 'E', the exponent sign, and the exponent, which has at most three digits. if (exp != 0) { result[index++] = 'E'; if (exp < 0) { result[index++] = '-'; exp = -exp; } if (exp >= 100) { result[index++] = (byte) ('0' + exp / 100); exp %= 100; result[index++] = (byte) ('0' + exp / 10); } else if (exp >= 10) { result[index++] = (byte) ('0' + exp / 10); } result[index++] = (byte) ('0' + exp % 10); } return index; }
private static int pow5bits(final int e) { return ((e * 1217359) >>> 19) + 1; }
// JIT somehow optimize this, and it's faster than performing log magic private static int decimalLength(final long v) { if (v >= 1000000000000000000L) return 19; if (v >= 100000000000000000L) return 18; if (v >= 10000000000000000L) return 17; if (v >= 1000000000000000L) return 16; if (v >= 100000000000000L) return 15; if (v >= 10000000000000L) return 14; if (v >= 1000000000000L) return 13; if (v >= 100000000000L) return 12; if (v >= 10000000000L) return 11; if (v >= 1000000000L) return 10; if (v >= 100000000L) return 9; if (v >= 10000000L) return 8; if (v >= 1000000L) return 7; if (v >= 100000L) return 6; if (v >= 10000L) return 5; if (v >= 1000L) return 4; if (v >= 100L) return 3; if (v >= 10L) return 2; return 1; }
private static int pow5Factor(long value) { // We want to find the largest power of 5 that divides value. if ((value % 5) != 0) return 0; if ((value % 25) != 0) return 1; if ((value % 125) != 0) return 2; if ((value % 625) != 0) return 3; int count = 4; value /= 625; while (value > 0) { if (value % 5 != 0) { return count; } value /= 5; count++; } throw new IllegalArgumentException("" + value); }
/** * Compute the high digits of m * 5^p / 10^q = m * 5^(p - q) / 2^q = m * 5^i / 2^j, with q chosen * such that m * 5^i / 2^j has sufficiently many decimal digits to represent the original floating * point number. */ private static long mulPow5divPow2(final long m, final int i, final int j) { // m has at most 55 bits. final long mHigh = m >>> 31; final long mLow = m & 0x7fffffff; final long bits13 = mHigh * POW5_SPLIT[i][0]; // 124 final long bits03 = mLow * POW5_SPLIT[i][0]; // 93 final long bits12 = mHigh * POW5_SPLIT[i][1]; // 93 final long bits02 = mLow * POW5_SPLIT[i][1]; // 62 final long bits11 = mHigh * POW5_SPLIT[i][2]; // 62 final long bits01 = mLow * POW5_SPLIT[i][2]; // 31 final long bits10 = mHigh * POW5_SPLIT[i][3]; // 31 final long bits00 = mLow * POW5_SPLIT[i][3]; // 0 final int actualShift = j - 3 * 31 - 21; return (((((( ((bits00 >>> 31) + bits01 + bits10) >>> 31) + bits02 + bits11) >>> 31) + bits03 + bits12) >>> 21) + (bits13 >> actualShift; }
/** * Compute the high digits of m / 5^i / 2^j such that the result is accurate to at least 9 * decimal digits. i and j are already chosen appropriately. */ private static long mulPow5InvDivPow2(final long m, final int i, final int j) { // m has at most 55 bits. final long mHigh = m >>> 31; final long mLow = m & 0x7fffffff; final long bits13 = mHigh * POW5_INV_SPLIT[i][0]; final long bits03 = mLow * POW5_INV_SPLIT[i][0]; final long bits12 = mHigh * POW5_INV_SPLIT[i][1]; final long bits02 = mLow * POW5_INV_SPLIT[i][1]; final long bits11 = mHigh * POW5_INV_SPLIT[i][2]; final long bits01 = mLow * POW5_INV_SPLIT[i][2]; final long bits10 = mHigh * POW5_INV_SPLIT[i][3]; final long bits00 = mLow * POW5_INV_SPLIT[i][3]; final int actualShift = j - 3 * 31 - 21; return (((((( ((bits00 >>> 31) + bits01 + bits10) >>> 31) + bits02 + bits11) >>> 31) + bits03 + bits12) >>> 21) + (bits13 >> actualShift; }
} [/code] У меня возникли серьезные проблемы с поиском параметра с двойным значением для doubleToStream [list] [*]который будет охватывать последнюю строку функции int decimalLength(final long v) (в основном кажется, что его параметр dp в самом начале // шага 4 всегда >= 10)
[*]([b]СМОТРИТЕ СЛЕДУЮЩИЙ ПАРАГРАФ, Я ДЕЙСТВИТЕЛЬНО РЕШИЛ ЭТОТ ПУНКТ[/b]), который заставит функцию int pow5Factor(long value) возвращать значение > 4 (функция вызывается здесь только в том случае, если (q = q) { и только с mp в качестве параметра). Кажется, что внутренний цикл выполнит не более 1 итерации.
[/list] Я попробовал вернуться к математике, но делаю что-то не так, потому что всегда получаю двойное значение, которое не охватывает эти случаи. Если это действительно так и эти линии не могут быть покрыты, алгоритм действительно можно улучшить. Пожалуйста, помогите мне найти эти странные случаи. Обновление — пункт 2 выполнен — покрытие pow5Factor В итоге я написал довольно умный цикл, который перебирает все возможные значения mp, которые будут переданы в pow5Factor. Я не позволил программе завершиться, но в итоге получил следующие значения мантиссы, охватывающие случаи от 1 до 18: [code]0b1L, // pow5Factor(mp) == 1 0b101001L, // pow5Factor(mp) == 2 0b10111111L, // pow5Factor(mp) == 3 0b110111001L, // pow5Factor(mp) == 4 0b101101111101L, // pow5Factor(mp) == 5 0b110110100100101L, // pow5Factor(mp) == 6 0b10110000101001001L, // pow5Factor(mp) == 7 0b10001000100001010111L, // pow5Factor(mp) == 9 0b111101101111001101111111L, // pow5Factor(mp) == 10 0b11010010101111111101100011L, // pow5Factor(mp) == 11 0b10100110000010101100010010001L, // pow5Factor(mp) == 12 0b110001110110111110110100110011L, // pow5Factor(mp) == 13 0b1001110111111011111000100111011011L, // pow5Factor(mp) == 14 0b101011111110101110010001010101010001L, // pow5Factor(mp) == 15 0b1100100110100101100111010100001101011L, // pow5Factor(mp) == 16 0b110000001000010100110001000011111101101L, // pow5Factor(mp) == 17 0b110010011011001101100010010100001100000001L, // pow5Factor(mp) == 18 [/code] Цикл, который я написал: [code]private static final long mantissaMask = mantissaLimit - 1L;
private static void printLog(final long mp) { long mv = mp - 2; long m2 = mv >>> 2; long ieeeMantissa = m2 & mantissaMask; int p5f = pow5Factor(mp); System.out.println( "0b" + Long.toBinaryString(ieeeMantissa) + "L, // pow5Factor(mp) == " + p5f ); }
private static int pow5Factor(long value) { // We want to find the largest power of 5 that divides value. if ((value % 5) != 0) return 0; if ((value % 25) != 0) return 1; if ((value % 125) != 0) return 2; if ((value % 625) != 0) return 3; int count = 4; value /= 625; while (value > 0) { if (value % 5 != 0) { return count; } value /= 5; count++; } throw new IllegalArgumentException("" + value); }
public static final void main(final String[] ignored) { long mp = ((mantissaLimit + 1) mv % 5 != 0 -> OK p5f = pow5Factor(mp); if (p5f > max) { max = p5f; printLog(mp); } mp += mpStep; // 2 step -> mv % 5 != 0 -> OK p5f = pow5Factor(mp); if (p5f > max) { max = p5f; printLog(mp); } mp += mpStep; // 3 step -> mv % 5 != 0 -> OK p5f = pow5Factor(mp); if (p5f > max) { max = p5f; printLog(mp); } mp += mpStep; // 4 step -> mv % 5 == 0 -> NOT OK!!!!!!! SKIP!!!! mp += mpStep; } } [/code] Решение покрытия decimalLength может быть сложнее, поскольку оно находится гораздо глубже внутри функции fillBuffer.
Мобильная версия