Простой способ деления целого числа на 3

Я работаю над проектом, который должен сделать простой музыкальный проигрыватель на FPGA. Он берет музыкальный файл указанного формата с ПК и воспроизводит его вслух в виде петель.

Нам нужно реализовать стандартные длины нот, то есть Quaver для половины такта, Minim для 2 тактов и т. Д. В настоящее время у нас есть таблица длин тактов в количестве тактов при различных значениях BPM. Нам нужно умножить их на эти длины нот, чтобы получить правильные тактовые циклы. Единственная проблема - это Tuplet, что составляет треть от полного ритма.

Без реализации полномасштабной делительной схемы, есть ли какие-нибудь математические приемы, которые можно сделать, чтобы разделить, приблизительно, целое число на 3?

Источник

3 ответа

Решение

Деление на 3 аналогично умножению на 1/3 (=0,33333). 0,3333 можно выразить как сложение двух или более (в зависимости от необходимой точности) (слева) смещенных входных значений.

input*2^-a + input*2^-b + input*2^-c ...

Просто найдите подходящие значения для a, b, c,...

Это работает для (почти) всех подразделений.

Источник

Ниже приведен перевод VHDL-кода из "Хакерского восторга" Хэнка Уоррена. Он делит целое число без знака на постоянное значение 3, используя только сдвиги, сложения и умножения на постоянные значения 3 и 5 (которые также могут быть сведены к сдвигам и сложениям).

-- q is quotient, d is dividend
q := (d srl 2) + (d srl 4); -- q = d*0.0101 (approx)
q := q + (q srl 4); -- q = d*0.01010101
q := q + (q srl 8);
q := q + (q srl 16);
r := resize(d - q * 3, 32); -- 0 <= r <= 15.
q := resize(q + (5 * (r + 1) srl 4), 32);
Источник

Если точный результат целочисленного деления на 3 (x / 3) требуется для беззнакового значения длины LEN, тогда усечение целочисленных операций может быть использовано с небольшой хитростью. Константа для 1/3 должно быть длины LEN + 1 и 1 следует добавить. Затем можно использовать усечение. Псевдокод как:

C = 2 ** (LEN + 1) / 3 + 1
y = (x * C) / 2 ** (LEN + 1)

Функция Python, которая показывает и тестирует алгоритм для всех значений:

def div_by_3_test(LEN):
    DIVISOR = 3
    C = 2 ** (LEN + 1) // DIVISOR + 1
    for x in range(2 ** LEN):
        if (x * C) // 2 ** (LEN + 1) != x // DIVISOR: exit('Failed')

Модуль VHDL, который реализует это как:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity div_by_3 is
  generic(
    LEN : natural := 12);
  port(
    x_i   : in  std_logic_vector(LEN - 1 downto 0);
    y_o   : out std_logic_vector(LEN - 1 downto 0));
end entity;

architecture syn of div_by_3 is
  -- Constant to multiply, basically 1/3, but adding 1 to avoid error
  constant C : std_logic_vector(LEN - 1 + 1 downto 0) :=
    std_logic_vector(to_unsigned(2 ** (LEN + 1) / 3 + 1, LEN + 1));
  -- Intermediate, with length as 2 * LEN + 1
  signal t : std_logic_vector(2 * LEN + 1 - 1 downto 0);
begin
  -- Intermediate with full length result
  t <= std_logic_vector(unsigned(C) * unsigned(x_i));
  -- Result after truncation for division by LEN + 1
  y_o <= t(2 * LEN + 1 - 1 downto LEN + 1);
end architecture;

Преимущество состоит в том, что деление на 3 LEN номер бита может быть сделан за один цикл, используя только один 2 * LEN + 1 битовое умножение.

Могут быть добавлены регистры, чтобы обеспечить конвейер для высокоскоростного проектирования.

Обратите внимание, что аналогичная схема возможна для любого делителя, но длина C должен быть LEN + ceil(log2(DIVISOR)), с C масштабируется соответственно. Пожалуйста, смотрите https://math.stackexchange.com/q/2444306/275980 относительно математического обоснования.

Источник

Как упоминалось в dieli, умножьте на 0,333333.

Однако вместо использования нескольких отрицательных степеней двойки (то есть a, b, c,..) просто умножьте 1/3 на некоторую большую степень 2, например, 2^24 * (1/3) = 5592405. После умножения часов циклов и 5592405, просто разделите на 2 ^ 24.

B = (такты)*5592405

результат = B/2^24

Размер B будет зависеть от максимального размера тактовых циклов и может быть вычислен с помощью

максимальный размер регистра для B = целое число ( (log10((максимальный размер тактовых циклов)*5592405)/log10(2)) + 0,5)

Источник
Другие вопросы по тегам