Перейти к содержанию
Авторизация  
VShaclein

Частное от деления большого числа на 255

Рекомендуемые сообщения

как можно быстро (быстрее, чем n^1.5) найти сабж ?

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


Ссылка на сообщение

Мне кажется посмотреть в сторону двоичного сдвига на 8 и близости 255 к 256..

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


Ссылка на сообщение

так в общем-то ноги оттуда и растут - нужно преобразовать число по основанию 256 в число по основанию 255

математики на ихнем форуме спеклись, им бы только подставные задачки решать

гугель говорит о том, что есть такой алгоритм флетчера, и остаток от деления равен сумме цифр, это быстро

т.е. можно быстро найти число, которое без остатка делится на 255

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


Ссылка на сообщение

как можно быстро (быстрее, чем n^1.5) найти сабж ?

VShaclein!

Что такое n в данном случае?

Какой нибудь алгоритм обещает быстрее в общем случаи, или Вы рассчитываете обыграть тот факт, что числа отличабтся только на единицу?

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

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


Ссылка на сообщение

VShaclein!

Правильно ли я понял, что есть чтсло

 

a0*256^0 + a1*256^1 + a2*256^2 + .... + am*256^m

 

и надо превратить это число в числс

 

b0*255^0 + b1*255^1 + b2*255^2 + .... + bl*255^l

 

где в общем случаи l не равно m

 

?

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

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


Ссылка на сообщение

совершенно правильно, в общем случае l >= m

вполне устраивает частный случай, когда m <= 176, когда для изменения основания достаточно одного дополнительного бита, т.е. l = m + 1/8

на практике m вряд ли будет превышать даже 32 или 64, среднестатистически скорее где-то 16

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

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


Ссылка на сообщение
Что такое n в данном случае?

длина числа в цифрах (байтах)

 

Какой нибудь алгоритм обещает быстрее в общем случаи,

деление столбиком обещает где-то n^1.5

я смутно помню из дискретной математики, что есть деление начиная с младших разрядов, что конкретно уже не помню, не исключено, что его как-то можно объединить с алгоритмом флетчера за раз вычисляя и частное и остаток, при этом сумма цифр для вычисления остатка для следующей иттерации может вычисляться путем вычитания текущей цифры из текущей суммы

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

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


Ссылка на сообщение

длина числа в цифрах (байтах)

VShaclein!

На русский переводится:

"Количество цифр в записи числа по основанию 10"?

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

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


Ссылка на сообщение

по основанию 256, одна цифра - один байт

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


Ссылка на сообщение

совершенно правильно, в общем случае l >= m

вполне устраивает частный случай, когда m <= 176,

VShaclein!

Можно узнать что это за физическоя величина, диапазон изменения которой, разделен на 256^176 интервалов?

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


Ссылка на сообщение

что, на этом всё ? это способ кодирования конца пакета в потоке данных - блок данных преобразуется так, чтобы исключить все байты с кодом 255, который далее и используется для кодирования конца/(начала) пакета

это красивый математический алгоритм, которым хочется заменить более другой, который сейчас используется

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

достоинство - сложность где-то пропорционально n

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

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


Ссылка на сообщение

Для публикации сообщений создайте учётную запись или авторизуйтесь

Вы должны быть пользователем, чтобы оставить комментарий

Создать учетную запись

Зарегистрируйте новую учётную запись в нашем сообществе. Это очень просто!

Регистрация нового пользователя

Войти

Уже есть аккаунт? Войти в систему.

Войти
Авторизация  

  • Последние посетители   0 пользователей онлайн

    Ни одного зарегистрированного пользователя не просматривает данную страницу

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

Важная информация

Мы разместили cookie-файлы на ваше устройство, чтобы помочь сделать этот сайт лучше. Вы можете изменить свои настройки cookie-файлов, или продолжить без изменения настроек.