caxapa.ru :: Я же сказал, что диапазон входных значенией - 0...N-1. На этих значениях преобразование однозначно. И как вы в формуле x=floor(sqrt(2*y)) учли mod N?

Сергей Борщ (01.04.2009 13:30, просмотров: 179) ответил Рэйлвэй Каген на Для (x*(x+1)/2)>=N не существует взаимно однозначного обратного преобразования.

Я же сказал, что диапазон входных значенией - 0...N-1. На этих значениях преобразование однозначно. И как вы в формуле x=floor(sqrt(2*y)) учли mod N?

Ответить

- Просто квадратное уравнение направильно составлено. Надо так: ReAl(697 знак., 01.04.2009 14:08)
  - k=[0,N/2], причем единственное, но от этого не сильно легче. - amusin(01.04.2009 14:52)
    - K<(N-1)/2, а если учесть, что К-целое, то N/2 надо бы исключить. Но это несущественно сократит поиск. - Рэйлвэй Каген(01.04.2009 15:01)
      - Ну да, про бесконечность - это от разворачивания mod, дальше понятно, что надо накладывать ограничения задачи. Но как-то оно явно не хочет быть симметричным по затратам. - ReAl(01.04.2009 16:17)
        
        Вот еще что придумал: y(x) = (y(x-1) + x) mod N. Поэтому если из y вычитать по модулю N числа 1,2,3,4, то на шаге x получится ноль. То же количество итераций, что и перебором, но вместо умножения x и деления на 2 - вычитание. - Сергей Борщ(02.04.2009 03:22)
        
        Решение найдено. Спасибо коллегам с Электроникса, которые напрягли математиков на форуме НГУ :) Если кому интересно - по ссылке. - Сергей Борщ(02.04.2009 18:39, ссылка)
        
        Развернул рекурсию. Это какой же склад ума надо уметь, чтобы писать рекурсию прямо из головы? Сергей Борщ(387 знак., 04.04.2009 13:04)
        
        Вполне обычный. Мы тут все забыли, как складывать лист бумаги :). А оно вон как выходит -> - Рэйлвэй Каген(04.04.2009 14:45, картинка)
        
        Класс! - Рэйлвэй Каген(03.04.2009 09:03)
- Да, я уже заметил. А формула работает только в области (x*(x+1)/2)<N, т.е. до первого разрыва. - Рэйлвэй Каген(01.04.2009 13:36)

Средства и методы разработки