Преобразование многочленов в нормализованную форму

Question

Кто-нибудь знает для уравнений вида

2 ⁿ + (–2) ^{n - 1} + ... + 2 ^{- n} + (–2) ^{- n + 1} + ... = у

Как убрать все коэффициенты (не экспоненциальные) минусы?Я знаю, что такое n , но я не могу вычислить их, чтобы найти y .

Например:

2 ⁴ - 2 ² + 2 упрощается до 2 ³ + 2 ² + 2

или

2 ⁴ - 2 ³ + 2 - 2 ^-1 + 2 ^-2 упрощается до 2 ³ + 2 ⁰ + 2 ^-1 + 2 ^-2

• y может быть нулем, но никогда не может быть отрицательным.Это будет помечено как ошибка.
• Все числа являются логами ₂ .
• Коэффициент всегда будет либо 1, либо -1.
• НетДопускается использование чисел с плавающей точкой или рациональных чисел.

Цель состоит в том, чтобы я хотел сохранить массивы показателей (положительных или отрицательных), но не коэффициентов, и мне нужно, чтобы полиномы были в нормализованной форме для удобства сравнения.

Есть ли название для этого типа преобразования?

Answer 1

Если вам нужен алгоритм, просто выберите отрицательный термин и конвертируйте: -2 ⁿ => -2 ^{n + 1} + 2 ⁿ , затемпо возможности отмените условия (например, 2 ^{n + 1} -2 ^{n + 1} => 0).Повторяйте, пока больше не будет отрицательных терминов.

Answer 2

Кажется, вы можете представить положительные элементы в двоичном представлении целого числа и то же самое с отрицательными. Например: 2^4 – 2^2 + 2 становится 10010 (положительные элементы) и 00100 (отрицательные элементы). Затем вычтите отрицательное целое число из положительного целого числа (вы получите 01110, переведенное обратно: 2^3 + 2^2 + 2)

Конечно, вам нужно убедиться, что вы можете хранить все значения (например, если у вас есть компоненты 2 ^ 100, встроенный целочисленный тип не будет достаточным - вам понадобится как минимум 100-битное целое число (больше) если у вас отрицательные показатели, смотрите ниже)). На этом этапе вы можете свернуть свою собственную реализацию (или найти библиотеку BigInt).

Кроме того, вам нужно будет отслеживать, какой битовый индекс представляет какой показатель - в приведенном выше примере это тривиально, поскольку все показатели были неотрицательными, но вам нужно немного сместить отрицательные показатели (например, 2^4 – 2^3 + 2 – 2^-1 + 2^-2 переводится в 10010.01 (+) и 01000.10 (-) с точкой (.), представляющей деление между неотрицательными и отрицательными показателями, в результате чего получается 01001.11 или 2^3 + 2^0 + 2^-1 + 2^-2).