Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
0
#include <inttypes.h>
uint64_t pow_(uint64_t num, uint8_t pow)
{
static const void *array_pow[] = { &&l0, &&l1, &&l2, &&l3, &&l4, &&l5, &&l6,/* ....*/ };
uint64_t ret = 1;
goto *array_pow[pow];
/* ... */
l6: ret *=num;
l5: ret *=num;
l4: ret *=num;
l3: ret *=num;
l2: ret *=num;
l1: ret *=num;
l0:
return ret;
}
Царский анролл возведения в степень через gcc-шные goto. Сам придумал. Но тут еще вот какая западня. Оптимизируется он хреново. Например, если взять возведение в степень 6 http://goo.gl/6SK2et
то можно обойтись 3 инструкциями imul в то время как в хрени с метками их целых 6.
Запостил: 
j123123,
(Updated )
1. Избавиться от "лишней" инструкции перехода (и dec)
2. Избавиться от инструкции перехода, ломающей бранч-предиктор
3. Использовать в разных ветках цикла разные регистры чтобы команды бежали параллельно
goto не позволяет выполнить ни первое ни второе условие 🙂 Да и не думаю, что jmp *rax также хорошо реализован в предсказателях
А общая переменная ret ломает третье (хотя его, наверное, можно как-то соблюсти).
Всего 4 штуки.
Ну не верю я в крутизну компиляторов, глядя на все это безобразие
Я тебе попытался объяснить что на IAR своя конвенция, и трахания с байт-свопом можно просто полностью обойти. Во-первых. Во-вторых, сила компилера не в том как он отдельно-стоящую функцию оптимизирует - а как он целую программу оптимизирует.
Это грех перед лицом б-га. Покайтесь, пока-а-айтесь, греховодники!..
То, что коммерческие компиляторы однозначно всегда круче опенсорсных - миф. Да, наверняка есть какие-то там коммерческие компиляторы под экзотические платформы, на которых опенсорсных компилей или нет вообще, или они там плохо оптимизируют (например какой-нибудь SDCC), но это просто потому, что никто этими опенсорсными компиляторами под эмбеддед не занимается плотно
https://web.archive.org/web/20130203094813/http://www.insidepro.com/kk/031/031r.shtml
Оптимизация switch
Балансировка логического древа
1. зачем лейблы если можно по индексу свитч делать? но это не самое главное.
2. почитай про алгоритмы возведения в степень. проблема не новая. тупое гугление даёт например:
http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int
Именно поэтому я этот говнокод тут разместил
>1. зачем лейблы если можно по индексу свитч делать?
Свич не гарантирует что это будет переведено в нужную форму. Возможно что какой-то комплиятор налепит там кучу cmp je инструкций. Если через метки на лейблы нельзя, можно сделать кучу функций для возведения в степень от 1 до n и сделать массив указателей на функции, потом вызывать их в зависимости от того, в какую степень возводится
>2. почитай про алгоритмы возведения в степень. проблема не новая.
Надо специализированный JIT писать для возведения в степень для бигинтов короче
> Свич не гарантирует что это будет переведено в нужную форму.
потому что пара тиков для предсказуемого джампа + префетч будут таким большим тормозом по сравнению с умножением... *roll eyes* *premature optimization is root of all evil*
> > 2. почитай про алгоритмы возведения в степень. проблема не новая.
> Надо специализированный JIT писать для возведения в степень для бигинтов короче
зачем тебе вообще возведение в степень надо?
Ну, может я пишу свою CAS и у меня бигинты и надо чтоб большие степени быстро возводить всякие там
Поэтому используется GCC-изм, чтобы гарантировать, какой компилер и что будет лепить? 🙂
http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int
- "squaring".
даже компилер ему выше (возведение в константную степень 16) это как бы пытается подсказать.
Дык умножение на современных процах и так выполняется примерно как сложение... У аппаратного умножителя, емнип, самый тормоз в том же месте, где и у сумматора - в распространении переноса на всю длину регистра в самом-самом конце.
Вот умножение чисел произвольной размерности - да, серьёзно можно оптимизнуть. Почитай в GMP как они это делают. Там очень нетривиальные алгоритмы, никак не связанные с байтоёбством.
Но там не рассматривается сценарий, когда мы неким хитрым образом анализируем само число и делаем через JIT некую специализированную функцию, которая потом это все очень быстро умножает через сдвиги какие-нибудь
Ну а для пачек подряд идущих умножений (возведение в степень) всякие монтгомери есть, которые тоже делают меньше действий. На RSAшных масштабах профит, емнип, тоже есть.
Multiplication of large long integers is now much faster thanks to an implementation of Karatsuba multiplication, an algorithm that scales better than the O(n*n) required for the grade-school multiplication algorithm. (Original patch by Christopher A. Craig, and significantly reworked by Tim Peters.)
#define MPD_KARATSUBA_BASECASE 16
The version of BigInteger in jdk8 switches between the naive algorithm, The Toom-Cook algorithm, and Karatsuba depending on the size of the input to get excellent performance.
Умножение-в-столбик-бляди соснули?
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java#l1471
P.S. Ну вот FFT не завезли, но это и понятно, числа по 30000+ бит на практике хуй найдёшь.
Получишь конфетку красный богатырь
А вот хер тебе
private static final int KARATSUBA_SQUARE_THRESHOLD = 128;
4 кибилота
Можешь еще тут почитать http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java#l1883
Он когда появился, кстати, неужто в 8? Жавабляди и тут соснули? (я в старой версии изучал)
Никогда не слышал о более-менее вменяемых хотябы за N^2
И я не думаю, что это будет работать так же быстро, как и умножение.
Почитал на русской педии - так и не понял что он дает. Один хер там нужно большое число нужно брать по модулю большого числа (см. return у функции MonPro)
Может ты прояснишь?
Там, емнип, деление на n совсем читерское получается - сравнение да вычитание.
З.Ы. На русской вики хуйня какая-то вместо статьи. Посмотри английскую, там с примерами и т.п.
Так какая-то хуйня вместо русской вики
fixed
Прошло время и мир изменился. Сашка стал Александром Семеновичем, школа сменилась работой, беззаботное детство - ежедневной рутиной. Мороженное незаметно исчезло из его жизни совершенно неожиданно. В студенческие годы его заменило пиво, после - различные суши и роллы. Забылось-то самое ощущение приятной прохлады и сладких липких пальцев
Как-то после работы Александру Семеновичу позвонили. Он снял трубку и услышал голос своей беременной жены
- Саш, купи мороженное.
- Какое опять мороженное?
- Хочется. Пломбира. Шоколадного
- С вафелькой?
- Да, конечно с вафелькой.
- Штукатуркой сверху намазать?
- Дурак ты, Саша. -ответила жена и положила трубку.
По пути домой Александр Семенович заехал в магазин и, подойдя к стойке с мороженным, увидел давно забытое им лакомство. "48 копеек. Шоколадное" - гласила надпись на несколько изменившийся упаковке. В порыве ностальгии он купил сразу все брикеты, коих насчиталось 28 штук.
- Я трубую менеджера - сказал он молодой кассирше, которая была так испугана его гневным взглядом, что не смогла ничего возразить.
Менеджер был значительно моложе и гораздо гораздо наглее Александра Семеновича
- Так это не то мороженное. Тут нет надписи "нестле". Это наше, российское. с местного молокозавода.
- А где тогда то само, не российское?
- А нигде. Импортозамещение
Мужчина хотел что то ответить, но замер с открытым ртом. Он поставил пакет на кассу и молча вышел из магазина. впервые за много лет ему стало так обидно, что по щеке покатилась скупая слеза
>Nestle
Толсто же.
fixed #2
Вот оно после каждого умножения и берет модуль. Алгоритм не осилил, и, скорее всего, и не осилю, т.к. уже вышел из среды в которой это изучали.
Касательно нашего обсуждения- какая там сложность?
Только хз почему его не юзают в стандартных библиотеках питона и джавы.
А если найду?
https://github.com/python/cpython/blob/1fe0fd9feb6a4472a9a1b186502eb9c0b2366326/Modules/_decimal/libmpdec/mpdecimal.c#L5484
1024 блока (32000+ бит) получается
Надо короче компилтайм макросы с гомоиконностью в сях лепить, чтоб можно было писать обычный двоичный поиск, и потом анролить его в нужных местах