Спасибо!

Языки программирования и методы трансляции. Лекция 9.
https://www.youtube.com/watch?v=Z61DWu3kFms&feature=youtu.behttps://www.youtube.com/watch?v=Z61DWu3kFms&feature=youtu.be
Единственная в мире программа, не содержащая ошибок! Ура! В языке "О" появляются процедуры! И функции. С параметрами и без параметров. С локальными переменными и без них. С параметрами-значениями и параметрами-переменными. Обсуждаем пролог и эпилог. Доступ с локальным переменным, параметрам значениям и параметрам-переменным. Ханойские башни на языке "О" с процедурами.

Конструкция простого ассемблера. Ассемблер - это не язык, как многие думают. Потому что ассемблер двухпроходный. Язык же не бывает двухпроходным...

Программы с лекции здесь: https://t.me/c3c_education/2283

Еще одна лекция и я больше так не буду.

Ктонибудь знает эффективный алгоритм вычисления целочисленного логарифма с произвольным основанием? Требования достаточно необычные - нельзя использовать плавающую арифметику ну алготим должен быть как можно более бысртым и корректно отрабатывать всегда. Например первое что приходит в голову это:

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].

Все это нужно для подсчета колличества цифр необходимых для представления в виде строки.
Я встречал подход еще с бинарным поиском, но он требует возведения в степень и все это в цикле, в общем тоже весьма сомнительное удовольствие

А что там делают эти всякие мегабыстрые сериализаторы JSON?

Выделяют с запасом?

да, обычно выделяют с запасом

вообще это проблема дискретного логарифма но в лайтовой форме

Вообще может пригодиться построить таблицы

Чем бинарный поиск по таблице не нравится?

Думал об этом. Построить таблицу для 0xFFFF / log2(base) от 2 до 36 и потом использовать fixed point арифметику а для делимого использовать clz(x) с пост коррекцие, но что то мне подсказывает, что можно сделать проще

Да можно все таблицы построить

Они ж небольшие выходят

тут еще одна проблема вылазит, это нужно сделать как можно компакнее) Поэтому если и таблица то небольшая

Вообще нужно какое то решение в стиле hacker’s delight

Сколько?)

Ты можешь занести в таблицу значения переполнения, например

И тогда за одно сравнение получаешь решение проблемы переполнения

Таблицы можно прореживать, если нужно место экономить

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