M
Вот кстати с бинарным поиском на схеме:
http://programmingpraxis.codepad.org/M5U3EZEv
http://programmingpraxis.codepad.org/M5U3EZEv
a_next = a * radix;
if (a_next < a)
// overflow
else
a = a_next;
Size: a a a
2020 May 19
MM
Артём ИМХО хорошую идею предложил:
AD
Артём ИМХО хорошую идею предложил:
a_next = a * radix;
if (a_next < a)
// overflow
else
a = a_next;
а вот тут я бы не был бы так уверен, не всегда a_next < a будет, кажется
MM
Да, похоже не всегда
AD
но таблица на 32 значения кажется совсем немного, нет?
AD
можно ее прямо в код вкомпилить
MM
Ещё можно умножать в 2 этапа:
Если x и y 64-битные, то переполнение возможно только в сдвиге и сложении, это легко проверить
a = 2^32*x+y
a*radix = ((x*radix)<<32) + y*radix
Если x и y 64-битные, то переполнение возможно только в сдвиге и сложении, это легко проверить
AD
Ещё можно умножать в 2 этапа:
Если x и y 64-битные, то переполнение возможно только в сдвиге и сложении, это легко проверить
a = 2^32*x+y
a*radix = ((x*radix)<<32) + y*radix
Если x и y 64-битные, то переполнение возможно только в сдвиге и сложении, это легко проверить
можно, но зачем?) одно сравнение всё равно побеждает)
AD
вообще когда возможно переполнение? когда результат функции будет максимальным, правильно?
AD
если это так, то действительно кажется достаточно одной проверки еще до запуска цикла
M
вообще когда возможно переполнение? когда результат функции будет максимальным, правильно?
Нет, переполнение может быть не только вы этом случае. В том то и вся проблема
AD
MaxGraey
Нет, переполнение может быть не только вы этом случае. В том то и вся проблема
а можно пожалуйста пример?
M
Да полно примеров:
ilogb(0xfffffffffffffffe, 3)
ilogb(0xfffffffffffffffe, 3)
AD
ilogb(u64(-1), 3) чему равно?
AD
вот тому же равен твой пример
AD
максимальному значению для конкретного base
AD
т.е. достаточно одной проверки
M
Ну смотри там t <= n, при этом t = t * base будет переполняться при любом слцчае когда clz(t) + clz(base) < 63 и даже иногда при < 62. А таких случаев полно
AD
MaxGraey
Ну смотри там t <= n, при этом t = t * base будет переполняться при любом слцчае когда clz(t) + clz(base) < 63 и даже иногда при < 62. А таких случаев полно
можно пожалуйста 1 конкретный пример? как-то не получается у меня осознать