Алгоритм преобразования десятичных дробей в отрицательные?

У меня есть двухэтапный алгоритм преобразования. Я не уверен, что это оптимальный алгоритм, но он работает довольно хорошо.

Основная идея состоит в том, чтобы начать с получения десятичного представления числа, а затем преобразовать это десятичное представление в непорядковое представление, обрабатывая четные степени и нечетные степени отдельно.

Вот пример, который мотивирует идею алгоритма. Это будет подробно описано, но в конечном итоге мы придем к алгоритму и в то же время покажем, откуда он взялся.

Предположим, мы хотим преобразовать число 0,523598734 в отрицательное десятичное число (обратите внимание, что я предполагаю, что вы можете преобразовать его в десятичное число). Заметь

0.523598734 =   5 * 10^-1
              + 2 * 10^-2
              + 3 * 10^-3
              + 5 * 10^-4
              + 9 * 10^-5
              + 8 * 10^-6
              + 7 * 10^-7
              + 3 * 10^-8
              + 4 * 10^-9

Поскольку 10^-n = (-10)^-n, когда n четно, мы можем переписать это как

0.523598734 =   5 * 10^-1
              + 2 * (-10)^-2
              + 3 * 10^-3
              + 5 * (-10)^-4
              + 9 * 10^-5
              + 8 * (-10)^-6
              + 7 * 10^-7
              + 3 * (-10)^-8
              + 4 * 10^-9

Перестановка и перегруппировка терминов дает нам следующее:

0.523598734 =   2 * (-10)^-2
              + 5 * (-10)^-4
              + 8 * (-10)^-6
              + 3 * (-10)^-8
              + 5 * 10^-1
              + 3 * 10^-3
              + 9 * 10^-5
              + 7 * 10^-7
              + 4 * 10^-9

Если бы мы могли переписать эти отрицательные члены как степени -10, а не степени 10, мы бы закончили. К счастью, мы можем сделать хорошее наблюдение: если d — ненулевая цифра (1, 2, ... или 9), то

  d * 10^-n + (10 - d) * 10^-n
= 10^-n (d + 10 - d)
= 10^-n (10)
= 10^{-n+1}

Переформулировано по-другому:

  d * 10^-n + (10 - d) * 10^-n = 10^{-n+1}

Таким образом, мы получаем этот полезный факт:

  d * 10^-n = 10^{-n+1} - (10 - d) * 10^-n

Если предположить, что n нечетно, то -10^-n = (-10)^-n и 10^{-n+1} = (-10)^{-n+1}. Таким образом, для нечетного n мы видим, что

  d * 10^-n = 10^{-n+1}    - (10 - d) * 10^-n
            = (-10)^{-n+1} + (10 - d) * (-10)^-n

Подумайте о том, что это означает в непорядковой системе счисления. Мы превратили степень десяти в сумму двух степеней минус десять.

Применение этого к нашему суммированию дает следующее:

0.523598734 =   2 * (-10)^-2
              + 5 * (-10)^-4
              + 8 * (-10)^-6
              + 3 * (-10)^-8
              + 5 * 10^-1
              + 3 * 10^-3
              + 9 * 10^-5
              + 7 * 10^-7
              + 4 * 10^-9
            =   2 * (-10)^-2
              + 5 * (-10)^-4
              + 8 * (-10)^-6
              + 3 * (-10)^-8
              + (-10)^0  + 5 * (-10)^-1
              + (-10)^-2 + 7 * (-10)^-3
              + (-10)^-4 + 1 * (-10)^-5
              + (-10)^-6 + 3 * (-10)^-7
              + (-10)^-8 + 6 * (-10)^-9

Перегруппировка дает следующее:

0.523598734 = (-10)^0
              + 5 * (-10)^-1
              + 2 * (-10)^-2 + (-10)^-2
              + 7 * (-10)^-3
              + 5 * (-10)^-4 + (-10)^-4
              + 1 * (-10)^-5
              + 8 * (-10)^-6 + (-10)^-6
              + 3 * (-10)^-7
              + 3 * (-10)^-8 + (-10)^-8
              + 6 * (-10)^-9

В целом, это дает отрицательное десятичное представление 1,537619346ND.

Теперь давайте подумаем об этом на отрицательном уровне. Заметь

• Цифры в четных позициях в основном сохраняются.
• Цифры в нечетных позициях переворачиваются: любая ненулевая нечетная цифра заменяется на 10 минус эта цифра.
• Каждый раз, когда переворачивается нечетная цифра, предыдущая цифра увеличивается.

Давайте посмотрим на 0,523598734 и применим этот алгоритм напрямую. Мы начинаем с того, что переворачиваем все нечетные цифры, чтобы получить их 10-е дополнение:

0.523598734 --> 0.527518336

Затем мы увеличиваем четные цифры, предшествующие всем перевернутым нечетным цифрам:

0.523598734 --> 0.527518336 --> 1.537619346ND

Это соответствует нашему предыдущему номеру, так что похоже, что у нас есть задатки алгоритма!

К сожалению, все становится немного сложнее, когда мы начинаем работать с десятичными значениями, включающими число 9. Например, давайте возьмем число 0,999. Применяя наш алгоритм, мы начинаем с перестановки всех нечетных цифр:

0.999 --> 0.191

Теперь мы увеличиваем все четные цифры, предшествующие столбцу, в котором было перевернуто значение:

0.999 --> 0.191 --> 1.1(10)1

Здесь (10) указывает, что столбец, содержащий 9, переполнился до 10. Очевидно, что это недопустимо, поэтому мы должны это исправить.

Чтобы понять, как это исправить, полезно посмотреть, как считать в негабинарном коде. Вот как считать от 0 до 110:

000
001
002
003
...
008
009
190
191
192
193
194
...
198
199
180
181
...
188
189
170
...
118
119
100
101
102
...
108
109
290

К счастью, здесь действительно хороший узор. Основной механизм работает как обычное приращение по основанию 10: увеличивается последняя цифра, и, если она переполняется, перенос 1 в следующий столбец, продолжая перенос, пока все не стабилизируется. Разница здесь в том, что столбцы с нечетными номерами работают в обратном порядке. Например, если вы увеличиваете цифру -10, вы на самом деле вычитаете единицу, а не добавляете ее, поскольку увеличение значения в этом столбце на 10 соответствует включению в вашу сумму на единицу -10 меньше. Если это число становится меньше 0, вы сбрасываете его обратно на 9 (вычитая 90), а затем увеличиваете следующий столбец (добавляя 100). Другими словами, общий алгоритм увеличения отрицательного числа работает следующим образом:

• Начните с 1-й колонки.
• If the current column is at an even-numbered position:
  • Add one.
  • Если значение достигает 10, установите его равным нулю, а затем примените эту процедуру к предыдущему столбцу.
• If the current column is at an odd-numbered position:
  • Subtract one.
  • Если значение достигает -1, установите его равным 9, а затем примените эту процедуру к предыдущему столбцу.

Вы можете убедиться, что эта математика работает, обобщив приведенные выше рассуждения о цифрах -10s и 100s и поняв, что переполнение столбца с четным номером, соответствующего 10^k, означает, что вам нужно добавить 10 ^k+1, что означает, что вам нужно уменьшить предыдущий столбец на единицу, а уменьшение значимости столбца с нечетным номером работает путем вычитания 9 10^k, а затем добавления 10^к+1.

Вернемся к нашему примеру. Мы пытаемся преобразовать 0,999 в десятичную дробь, и у нас получилось

0.999 --> 0.191 --> 1.1(10)1

Чтобы исправить это, мы возьмем столбец 10 и сбросим его обратно на 0, а затем перенесем 1 в предыдущий столбец. Это столбец с нечетным номером, поэтому мы уменьшаем его значение. Это дает окончательный результат:

0.999 --> 0.191 --> 1.1(10)1 --> 1.001ND

В целом, для положительных чисел у нас есть следующий алгоритм преобразования:

• Processing digits from left to right:
  • If you're at an odd-numbered digit that isn't zero:
    • Replace the digit d with the digit 10 - d.
    • Используя стандартный алгоритм сложения негадальных чисел, увеличьте значение в предыдущем столбце.

Конечно, отрицательные числа — это совсем другая история. С отрицательными числами нечетные столбцы верны, а четные столбцы необходимо перевернуть, так как четность (-10)^k членов в суммирующем флипе. Следовательно, для отрицательных чисел вы применяете описанный выше алгоритм, но сохраняете нечетные столбцы и переворачиваете четные столбцы. Точно так же вместо увеличения предыдущей цифры при переворачивании вы уменьшаете предыдущую цифру.

В качестве примера предположим, что мы хотим преобразовать -0,523598734 в отрицательный десятичный вид. Применение алгоритма дает следующее:

-0.523598734 --> 0.583592774 --> 0.6845(10)2874 --> 0.684402874ND

Это действительно правильное представление.

Надеюсь это поможет!

На ваш вопрос я подумал об этом объектно-ориентированном коде. Хотя я не уверен. Этот класс принимает два недесятичных числа с помощью оператора и создает уравнение, а затем преобразует эти числа в десятичные числа.

public class NegadecimalNumber {
private int number1;
private char operator;
private int number2;

public NegadecimalNumber(int a, char op, int b) {
    this.number1 = a;
    this.operator = op;
    this.number2 = b;

}

public int ConvertNumber1(int a) {
    int i = 1;
    int nega, temp;
    temp = a;
    int n = a & (-10);
    while (n > 0) {
        temp = a / (-10);
        n = temp % (-10);
        n = n * i;
        i = i * 10;
    }
    nega = n;
    return nega;
}

public int ConvertNumber2(int b) {
    int i = 1;
    int negb, temp;
    temp = b;
    int n = b & (-10);
    while (n > 0) {
        temp = b / (-10);
        n = temp % (-10);
        n = n * i;
        i = i * 10;
    }
    negb = n;
    return negb;
}

public double Equation() {
    double ans = 0;
    if (this.operator == '+') {
        ans = this.number1 + this.number2;
    } else if (this.operator == '-') {
        ans = this.number1 - this.number2;
    } else if (this.operator == '*') {
        ans = this.number1 * this.number2;
    } else if (this.operator == '/') {
        ans = this.number1 / this.number2;
    }
    return ans;
}

}

Обратите внимание, что https://en.wikipedia.org/wiki/Negative_base#To_Negative_Base говорит вам как перевести целые числа в отрицательное основание. Таким образом, один из способов решить эту проблему — просто умножить дробь на достаточно высокую степень 100, чтобы превратить ее в целое число, преобразовать, а затем снова разделить: -0,06 = -6/100 => 14/100 = 0,14.

Другой способ - понять, что вы пытаетесь создать сумму в форме -a/10 + b/100 -c/1000 + d/10000... для аппроксимации целевого числа, поэтому вы хотите уменьшить ошибку настолько, насколько можно на каждом этапе, но нужно оставить ошибку в том направлении, которое вы сможете исправить на следующем этапе. Обратите внимание, что это также означает, что при преобразовании дробь может не начинаться с 0. 0,5 => 1,5 = 1 - 5/10.

Итак, чтобы преобразовать -0,06. Это отрицательное значение, и первая цифра после запятой находится в диапазоне [0,0, -0,1 .. -0,9], поэтому мы начинаем с 0, чтобы оставить нам -0,06 для преобразования. Теперь, если первая цифра после запятой равна 0, то у меня осталось -0,06, что в неправильном направлении для преобразования с 0,0d, поэтому мне нужно выбрать первую цифру после запятой, чтобы получить приближение ниже моей цели -0,06 . Поэтому я выбрал 0,1, что на самом деле равно -0,1, и дает мне ошибку 0,04, которую я могу точно преобразовать, оставив мне преобразование 0,14.

Итак, в каждой точке выведите цифру, которая дает вам либо

1) Точный результат, в этом случае вы закончили

2) приближение, которое немного больше целевого числа, если следующая цифра будет отрицательной.

3) приближение, которое немного меньше целевого числа, если следующая цифра будет положительной.

И если вы начнете пытаться аппроксимировать число в диапазоне (-1,0, 0,0] в каждой точке, вы можете выбрать цифру, которая сохраняет оставшуюся ошибку достаточно малой и в правильном направлении, так что это всегда работает.