Можно ли заменить последовательные усекающие целочисленные деления умножением?

Question

В математике начальной школы с рациональными числами выражение (a / b) / c эквивалентно a / (b * c) по базовым алгебраическим манипуляциям.

То же верно, когда / усекает целочисленное деление, как в C ибольшинство других языков?То есть можно ли заменить серию делений одним делением на произведение всех делителей?

Вы можете предположить, что умножение не переполняется (если это так, то очевидно, что они не эквивалентны).

Answer 1

Да, на целых числах. Кто-то уже опубликовал (и удалил?) Пример того, как он может не работать с плавающей запятой. (Хотя это может быть достаточно близко для вашего приложения.)

@ У Джона Колемана есть аргумент из теории, но вот аргумент из эксперимента. Если вы запустите этот код:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define LIMIT 100
#define NUM_LIMIT 2000

int main() {
    for(int div1 = -LIMIT; div1 < LIMIT; div1++) {
        for(int div2 = -LIMIT; div2 < LIMIT; div2++) {
            if(div1 == 0 || div2 == 0) continue;
            for(int numerator = -NUM_LIMIT; numerator < NUM_LIMIT; numerator++) {
                int a = (numerator / div1) / div2;
                int b = numerator / (div1 * div2);
                if(a != b) {
                    printf("%d %d\n", a, b);
                    exit(1);
                }
            }
        }
    }
    return 0;
}

Он пробует деление в обе стороны и сообщает об ошибке, если они различаются. Запуск его следующими способами не сообщает об ошибке:

• div1, div2 от -5 до 5 и числитель от -INT_MAX / 100 до INT_MAX / 100
• div1, div2 от -2000 до 2000 и числитель от -2000 до 2000

Поэтому я бы поспорил, что это будет работать с любыми целыми числами. (При условии, опять же, что div1 * div2 не переполняется.)

Answer 2

Экспериментально это помогает понять, как вы применяете математику.

Программное обеспечение не меняет математику, идентификационные данные или другие манипуляции, которые вы делаете для упрощения или изменения уравнения с использованием переменных. Программное обеспечение выполняет запрошенные операции. Фиксированная точка делает их отлично, если вы не переполнены.

И из математики, а не из программного обеспечения, мы знаем, что ни b, ни c не могут быть равны нулю, чтобы это сработало. Программное обеспечение добавляет, что b * c также не может быть нулем. И если он переполнен, то результат неправильный.

a / b / c = (a / b) * (1 / c) = (a * 1) / (b c) = a / (b c) из начальной школы, и вы можете Реализуйте a / b / c или a / (b * c) на вашем языке программирования, который вы выберете. В большинстве случаев, если вы придерживаетесь целых чисел, результаты неверны из-за того, что дробь не представлена. Значительное количество времени результаты неверны, если вы используете число с плавающей запятой, по той же причине, недостаточно бит для хранения бесконечно больших или маленьких чисел, как в случае с чистой математикой. Итак, где вы сталкиваетесь с этими пределами? Вы можете увидеть это с помощью простого эксперимента.

Напишите программу, которая просматривает все возможные комбинации чисел от 0 до 15 для a, b и c, вычисляет a / b / c и a / (b * c) и сравнивает их. Поскольку это четырехбитные числа, помните, что промежуточные значения также не могут превышать 4 бит, если вы хотите посмотреть, что с этим будет делать язык программирования. Печатается только деление на нули и те, где они не совпадают.

сразу же вы увидите, что если любое из значений будет равным нулю, для очень неинтересного эксперимента вы либо получите большое деление на нули, либо 0 / что-то_от_зеро не интересный результат.

 1  2  8 : divide by zero
 1  3 11 :  1  0
 1  4  4 : divide by zero
 1  4  8 : divide by zero
 1  4 12 : divide by zero
 1  5 13 :  1  0
 1  6  8 : divide by zero
 1  7  7 :  1  0
 1  8  2 : divide by zero
 1  8  4 : divide by zero
 1  8  6 : divide by zero
 1  8  8 : divide by zero
 1  8 10 : divide by zero
 1  8 12 : divide by zero
 1  8 14 : divide by zero
 1  9  9 :  1  0
 1 10  8 : divide by zero
 1 11  3 :  1  0
 1 12  4 : divide by zero
 1 12  8 : divide by zero
 1 12 12 : divide by zero
 1 13  5 :  1  0
 1 14  8 : divide by zero
 1 15 15 :  1  0
 2  2  8 : divide by zero
 2  2  9 :  1  0
 2  3  6 :  1  0
 2  3 11 :  2  0

так что до этого момента ответы совпадают. для небольшого a или, в частности, a = 1, имеет смысл, что результат будет 0 или 1. и оба пути приведут вас туда.

 1  2  8 : divide by zero

по крайней мере для a = 1, b = 1. с = 1 дает 1, остальные дают результат 0.

2 * 8 = 16 или 0x10, что является слишком большим количеством битов, поэтому оно переполняется, и в результате получается 0x0 с делением на ноль, так что вам нужно искать независимо от того, что, с плавающей запятой или с фиксированной точкой.

 1  3 11 :  1  0

первый интересный
1 / (3 * 11) = 1 / 0x21, что означает 1/1 = 1; 1/3 = 0, 0/11 = 0. поэтому они не совпадают. 3 * 11 переполнен.

и это продолжается.

так что увеличение ra может сделать это более интересным? небольшая переменная в любом случае будет давать результат 0 большую часть времени.

15  2  8 : divide by zero
15  2  9 :  7  0
15  2 10 :  3  0
15  2 11 :  2  0
15  2 12 :  1  0
15  2 13 :  1  0
15  2 14 :  1  0
15  2 15 :  1  0
15  3  6 :  7  0
15  3  7 :  3  0
15  3  8 :  1  0
15  3  9 :  1  0
15  3 10 :  1  0
15  3 11 : 15  0
15  3 12 :  3  0
15  3 13 :  2  0
15  3 14 :  1  0
15  3 15 :  1  0
15  4  4 : divide by zero
15  4  5 :  3  0
15  4  6 :  1  0
15  4  7 :  1  0
15  4  8 : divide by zero
15  4  9 :  3  0


15  2  9 :  7  0

15 / (2 * 9) = 15 / 0x12 = 15/2 = 7. 15/2 = 7; 7/9 = 0;

15  3 10 :  1  0
15  3 11 : 15  0

переполнение обоих случаев не интересно.

поэтому измените вашу программу так, чтобы она отображала только те, в которых результат не совпадает, но также нет переполнения b * c .... нет вывода. Нет никакого волшебства или разницы между выполнением этого с 4-битными значениями против 8-битных против 128-битных ... это просто позволяет вам получить больше результатов, которые могут сработать.

0xF * 0xF = 0xE1, и вы можете легко увидеть, что это делает длинное умножение в двоичном, в худшем случае, чтобы охватить все возможные значения N бит, вам нужно 2 * N бит, чтобы сохранить результат без переполнения. Таким образом, в обратном направлении для деления числитель N битов, ограниченный знаменателем числа бит N / 2, может охватывать все значения фиксированной точки каждого с результатом N битов. 0xFFFF / 0xFF = 0x101. 0xFFFF / 0x01 = 0xFFFF.

Так что, если вы хотите сделать эту математику и можете убедиться, что ни одно из чисел не превышает N битов, тогда, если вы выполняете математику, используя N * 2 битов. Вы не будете иметь многократных переполнений, у вас все еще будет беспокойство о делении на нули.

Чтобы продемонстрировать это экспериментально, попробуйте все комбинации от 0 до 15 от a, b, c, но сделайте математику с 8-битными переменными вместо 4 (проверка на деление на ноль перед каждым делением и выбрасывание этих комбинаций), и результаты всегда матч.

Так есть ли "лучше"?и умножение, и деление могут быть реализованы за один такт с использованием тонны логики или за несколько тактов с использованием экспоненциально меньшего значения, несмотря на то, что ваши документы по процессору говорят, что это один такт, он все равно может быть многократным, поскольку существуют конвейеры, и они могут скрывать 2 или4 цикла либо в некоторые трубы и сэкономить тонну чипов недвижимости.Или некоторые процессоры вообще не делят, чтобы сэкономить место.Некоторые ядра cortex-m из arm, которые вы можете скомпилировать для разделения на один или несколько часов, экономят место только тогда, когда кто-то умножает (кто умножает в своем коде ??? или делит ???).Вы увидите, когда будете делать такие вещи, как

x = x / 5;

в зависимости от цели и параметров компилятора и оптимизации, которые могут / будут реализованы как x = x * (1/5), а также некоторые другие движения, чтобы сделать эторабота.

unsigned int fun ( unsigned int x )
{
    return(x/5);
}

0000000000000000 <fun>:
   0:   89 f8                   mov    %edi,%eax
   2:   ba cd cc cc cc          mov    $0xcccccccd,%edx
   7:   f7 e2                   mul    %edx
   9:   89 d0                   mov    %edx,%eax
   b:   c1 e8 02                shr    $0x2,%eax
   e:   c3                      retq   

разделение доступно для этой цели, а также умножение, но умножение воспринимается лучше, возможно, из-за часов, возможно из-за других.

, поэтому вы можете захотеть взятьэто во внимание.

Если вы делаете a / b / c, вы должны проверить деление на ноль дважды, но если вы делаете a / (b + c), вы должны проверить только один раз.Проверка деления на ноль обходится дороже, чем сама математика для 1 или около 1 числа часов на инструкцию alu.Таким образом, умножение в идеале работает лучше, но есть возможные исключения из этого.

Вы можете повторить все это, используя числа со знаком.И то же самое верно.Если он работает для 4 битов, он будет работать для 8 и 16, 32, 64 и 128 и т. Д. ...

7 * 7 = 0x31
-8 * -8 = 0x40
7 * -8 = 0xC8

Это должно охватывать крайние значения, поэтому, если вы используете удвоенное число битов, чемваш худший случай, вы не переполнены.Вам все еще нужно проверять деление на ноль перед каждым делением, поэтому решение умножения приводит только к одной проверке на ноль.Если вы удваиваете количество битов, которое вам нужно, вам не нужно проверять умножение на переполнение.

Здесь нет никакой магии, это и было решено с помощью базовой математики.Когда я переполняюсь, используя карандаш и бумагу и без языка программирования (или калькулятора, как я сделал, чтобы сделать это быстрее), вы можете видеть, когда.Вы также можете использовать больше математики этой начальной школы.msbit of b для N битов это b [n-1] * 2 ^ (n-1), верно?с 4-битным числом без знака msbit будет 0x8, что равно 1 * 2 ^ (4-1);и это верно для остальной части b (b [3] * 2 ^ 3) + (b [2] * 2 ^ 2) + (b [1] * 2 ^ 1) + (b [0] * 2 ^0);То же самое для C, поэтому, когда мы умножаем их с помощью математики начальной школы, мы начинаем с (b [3] c [3]) (2 ^ (3 + 3)), если вы садитесь и решаете этоваш худший случай не может превышать 2 ^ 8.Можно также посмотреть на это так:

     abcd
*    1111
=========
     abcd
    abcd
   abcd
+ abcd
=========
  xxxxxxx

7 битов плюс возможность переноса, что делает его в общей сложности 8 битами.все простые математики начальной школы, чтобы увидеть, каковы потенциальные проблемы.

Эксперименты не покажут, что битовые комбинации не работают (деление на ноль не считается, что также не работает для a / b / c = a / (b * c)).Ответ Джона Колеманса, чтобы посмотреть на него под другим углом, может помочь понять, что все битовые комбинации будут работать.Хотя это были все положительные цифры.Это работает и для отрицательных чисел, пока вы проверяете все свои переполнения.

Answer 3

Ответ «да» (по крайней мере, для неотрицательных целых чисел).Это следует из алгоритма деления , в котором говорится, что для любых натуральных чисел a,d мы имеем a = dq+r для уникальных неотрицательных целых чисел q,r с 0 <= q <= d-1.В этом случае q равно a/d в целочисленном делении.

В a/b/c (с целочисленным делением) мы можем думать об этом в два этапа:

a = b*q_1 + r_1  // here q_1 = a/b and 0 <= r_1 <= b-1
q_1 = c*q_2 + r_2 // here q_2 = q_1/c = a/b/c and 0 <= r_2 <= c-1

Но тогда

a = b*q_1 + r_1 = b*(c*q_2 + r_2) + r_1 = (b*c)*q_2 + b*r_2 + r1

Обратите внимание, что 0 <= b*r_2 + r_1 <= b*(c-1) + b-1 = bc - 1

Из этого следует, что q_2 есть a/(b*c).Таким образом a/b/c = a/(b*c).