Да, распределение по корзинам получается очень неравномерное. Но из-за равномерного выбора каждой из 2^19 корзин, в среднем выходит 1.9: на каждую корзину с ~122 элементами 63 пустых.
Ширина края — 19. Т.е. 1000000 палиндромов-серединок распределяются по 2^19 корзин (в среднем по 1.9 в каждой корзине).
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Ширина края — 19. Т.е. 1000000 палиндромов-серединок распределяются по 2^19 корзин (в среднем по 1.9 в каждой корзине).
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Это не строгое доказательство, а попытка объяснить реальные результаты :)
Например, для ширины в 24 десятичных знака, и следовательно 900000 элементов А, проверено 3958921 палиндромов, в среднем по 4.4 различных b на каждый a.
В Европе даже премиальное авто дешевле такси с водителем. В Женеве, помню за 10 минут ночной поездки хотели около 2500 рублей. Я даже на последнюю ночь перебрался в гостиницу у аэропорта.
Человеческий глаз устроен так, что видит очень много новых машин премиальных марок. А вдесятеро больше унылых, старых и дешевых машин, не заезжающих в туристические места — не видит.
Когда я бываю в России (Санкт-Петербурге), мне кажется, что там чуть половина машин — премиальные марки. Но статистика утверждает, что среди первых 10 марок по продажам, премиальных марок нет.
Я только что посмотрел — на «случайный» доступ к этой огромной структуре тратится 70-80% всего времени, в разы больше чем на всю математику.
Но, если я не ошибаюсь, ваше ускорение не применимо в случае взаимно простых оснований.
Потому что ваш алгоритм уже быстрее O(N1/4)
Да, распределение по корзинам получается очень неравномерное. Но из-за равномерного выбора каждой из 2^19 корзин, в среднем выходит 1.9: на каждую корзину с ~122 элементами 63 пустых.
Это же мой алгоритм, у меня 2^19? Откуда вы вообще взяли число 13?
100000_000000000000_000001 = 1010100101101000000_1011000111111000010100101011110110100000000000000000000001
100001_000000000000_100001 = 1010100101101000100_0010101000100101111111111010011101111001011000011010100001
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Палиндромы-края изменяются от 100000хххххххххххх000001 до 999999хххххххххххх9999999, и для каждого палиндрома-края проверяется всего несколько корзин.
Например, для ширины в 24 десятичных знака, и следовательно 900000 элементов А, проверено 3958921 палиндромов, в среднем по 4.4 различных b на каждый a.
80 первых членов я нахожу за 3.5 секунды.
Человеческий глаз устроен так, что видит очень много новых машин премиальных марок. А вдесятеро больше унылых, старых и дешевых машин, не заезжающих в туристические места — не видит.
Когда я бываю в России (Санкт-Петербурге), мне кажется, что там чуть половина машин — премиальные марки. Но статистика утверждает, что среди первых 10 марок по продажам, премиальных марок нет.
Я же не спорю, что люди, которые могут позволить себе новый автомобиль премиальной марки, от них не откажутся.
Но, блин, таких людей МАЛО. МЕНЬШИНСТВО. А большинство ездит на таких машинах, на которые без слез взглянуть жалко.