Перейти к содержанию
    

Одним делением вычислить два

Если k1 не очень большое число (а k2 должно быть еще меньше, естественно), то второе деление можно заменить поиском по таблице, общим размером k1:

[0, 1, 2... k2-1], [0, 1, 2... k2-1], [0, 1, 2... k2-1], ...0, 1, ... (на каком-то числе закончится)

Тогда сначала нужно поделить на k1 и найти остаток, а потом по таблице по этому остатку-индексу найти остаток от деления на k2.

Не, таблица не вариант, памяти в обрез :(

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Не, таблица не вариант, памяти в обрез :(

Так а чем умножение на константу вместо деления на константу не устраивает?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Так а чем умножение на константу вместо деления на константу не устраивает?

Видимо, тем, что придется умножить на 1/k, затем из результата вычесть целую часть, оставить дробную, затем дробную умножить на k. Так получится остаток от деления на k. :)

P.S. Возможно, смайлик я поставил зря.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Видимо, тем, что придется умножить на 1/k, затем из результата вычесть целую часть, оставить дробную, затем дробную умножить на k. Так получится остаток от деления на k.

Ну да, примерно так, но не совсем.

Умножить на (65536 div k) (целая константа), выкинуть (просто игнорировать) 2 мл. байта – и частное готово. Для получения остатка нужно еще одно умножение и одно вычитание. И соответственно вместо второго деления тоже 2 умножения и одно вычитание. Все в целых числах.

По-моему, этим должно не не_устраивать, а как раз устраивать :) , ибо

 

Нужна реализация с одним делителем + умножители и сумматоры/вычитатели если нужно.

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

Конечно, из слов автора буквоед может сделать вывод, что непременно должно быть одно и только одно деление, но мы же не такие ;)

Хотя и в этом случае – пожалуйста: одно деление «честное», а вместо второго – как я сказал

Изменено пользователем Diusha

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

... но мы же не такие ;)

Мы не такие :rolleyes:

Как не-буквоеды мы можем сказать - что-то нечисто в самой постановке задачи. Оно точно такое надо?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Мы не такие :rolleyes:

Как не-буквоеды мы можем сказать - что-то нечисто в самой постановке задачи. Оно точно такое надо?

Спасибо за ответы, попробую.

Да, и оно точно так надо.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вот интересен например сам факт задачи, где топикстартер

утверждает, что у него ресурсов хватает на одно деление и

там пару умножений, но никак не на два деления.

Но если уж из железа вытянули все что можно - то это

признак некорректной имплементации и такой проект

может не иметь будущего даже если вы засунете два

последних умножения в кристалл как предлагается.

 

Когда в свое время было мало ПЗУ и еще меньше ОЗУ на

борту 8-ми битного железа, то все делали на целочисленной

арифметике подогнанной под границы 2^n ... заменяли

все что можно сдвигами - и получали неплохие результаты.

 

Будьте корректны с коллегами, поделитесь спецификацией

на часть данного приложения. ради спорта, ибо ради другого

просто не интересно.

 

 

 

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Видимо, тем, что придется умножить на 1/k, затем из результата вычесть целую часть, оставить дробную, затем дробную умножить на k. Так получится остаток от деления на k. :)
А если повезет с числами k1 и k2, то и этого не нужно будет :)

ТС, так какие там у Вас числа k1 и k2 ?

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

А если повезет с числами k1 и k2, то и этого не нужно будет :)

ТС, так какие там у Вас числа k1 и k2 ?

k2 = {2,4,6}

k1 - 27 значений может принимать, ну вот некоторые: 4024, 4650, 4482, 3776, 2832.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

k2 = {2,4,6}

k1 - 27 значений может принимать, ну вот некоторые: 4024, 4650, 4482, 3776, 2832.

ну тогда первое получение (а mod k1) таки честное деление

ну а деление на {2,4,6} с остатком это жеж совсем просто,

для 2 и 4 все совсем очевидно,

для 6 решается ну совсем простым домножением

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...