V\
MaxGraey
Ктонибудь знает эффективный алгоритм вычисления целочисленного логарифма с произвольным основанием? Требования достаточно необычные - нельзя использовать плавающую арифметику ну алготим должен быть как можно более бысртым и корректно отрабатывать всегда. Например первое что приходит в голову это:
ilogb(n: u64, base: i32) {
t = u64(base)
e = 1
while (t <= n) {
t *= base
e += 1
}
return e
}
Но у него есть проблема с переполнением например ilogb(u64(-1), 2) провалиться в бесконечный цикл из-за переполнения после умножения. Если добавить проверку на переполнение то это + 1 деление, +1 проверка условия в цикле, все это выходит очень недешево для base = 2, 3 …
Да base находиться в промежутке [2, 36].
Все это нужно для подсчета колличества цифр необходимых для представления в виде строки.
Я встречал подход еще с бинарным поиском, но он требует возведения в степень и все это в цикле, в общем тоже весьма сомнительное удовольствие
ilogb(n: u64, base: i32) {
t = u64(base)
e = 1
while (t <= n) {
t *= base
e += 1
}
return e
}
Но у него есть проблема с переполнением например ilogb(u64(-1), 2) провалиться в бесконечный цикл из-за переполнения после умножения. Если добавить проверку на переполнение то это + 1 деление, +1 проверка условия в цикле, все это выходит очень недешево для base = 2, 3 …
Да base находиться в промежутке [2, 36].
Все это нужно для подсчета колличества цифр необходимых для представления в виде строки.
Я встречал подход еще с бинарным поиском, но он требует возведения в степень и все это в цикле, в общем тоже весьма сомнительное удовольствие
Не помню есть ли там именно это, но попробуй fxtbook листануть