Возникла нужда проверить, является ли целое число квадратом, и если да, то вычислить корень. Причем хочется сделать это в целочисленной арифметике. Понятно, что можно реализовать метод Ньютона в целых числах, но он требует деления на каждом шаге. А нельзя ли по другому? Найти квадратный корень по модулю степени двойки, и проверить, а не будет ли он обычным квадратным корнем.
Читать полностью »
Рубрика «квадратный корень»
Вычисление целочисленного квадратного корня
2019-09-30 в 17:16, admin, рубрики: квадратный корень, математика, теория чиселТрехмерный движок внутри запроса SQL
2019-01-11 в 8:21, admin, рубрики: 3d, 3d-движок, phong, postgresql, ray marching, raymarching, sql, sqlite, аппроксимация, аппроксимация квадратного корня, вавилонский метод, затенение по фонгу, квадратный корень, любителей читать теги, магическая константа, метод герона, ненормальное программирование, погрешность, поздравляю с первой пятницей, рекурсивные запросы, трассировка лучей, трехмерный движокНесколько лет назад на форуме SQL.ru решили провести сравнение реализаций трассировщиков лучей на разных языках программирования. К сожалению, моя заявка не может участвовать т.к. она не выводит надпись «PIXAR», поэтому публикую ее здесь.
Для чистоты эксперимента я использовал SQLite без расширений. Оказалось, что там нет даже функции SQRT.
WITH RECURSIVE numbers AS (SELECT 0 AS n UNION ALL SELECT n+1 FROM numbers WHERE n<89),
pixels AS (SELECT rows.n as row, cols.n as col FROM numbers as rows CROSS JOIN numbers as cols WHERE rows.n > 4 AND rows.n < 38 AND cols.n > 9 AND cols.n < 89),
rawRays AS (SELECT row, col, -0.9049 + col * 0.0065 + row * 0.0057 as x, -0.1487 + row * -0.0171 as y, 0.6713 + col * 0.0045 + row * -0.0081 as z FROM pixels),
norms AS (SELECT row, col, x, y, z, (1 + x * x + y * y + z * z) / 2 as n FROM rawRays),
rays AS (SELECT row, col, x / n AS x, y / n AS y, z / n AS z FROM norms),
iters AS (SELECT row, col, 0 as it, 0 as v FROM rays UNION ALL SELECT rays.row, rays.col, it + 1 AS it, v + MAX(ABS(0.7+v*x) - 0.3, ABS(0.7+v*y) - 0.3, ABS(-1.1+v*z) - 0.3, -((0.7+v*x) * (0.7+v*x) + (0.7+v*y) * (0.7+v*y) + (-1.1+v*z) * (-1.1+v*z)) * 1.78 + 0.28) AS v FROM iters JOIN rays ON rays.row = iters.row AND rays.col = iters.col WHERE it < 15),
lastIters AS (SELECT it0.row, it0.col, it0.v AS v0, it1.v AS v1, it2.v AS v2 FROM iters as it0 JOIN iters AS it1 ON it0.col = it1.col AND it0.row = it1.row JOIN iters AS it2 ON it0.col = it2.col AND it0.row = it2.row WHERE it0.it = 15 AND it1.it = 14 AND it2.it = 13),
res AS (SELECT col, (v0 - v1) / (v1 - v2) as v FROM lastIters)
SELECT group_concat(substr('$@B%8&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/|()1{}[]?-_+~<>i!lI;:,"^. ', round(1 + max(0, min(66, v * 67))), 1) || CASE WHEN col=88 THEN X'0A' ELSE '' END, '') FROM res;
:++++I
_________________________"
------/jucYJLQ0OZmwwwwwwwmmZO0QCUXcnj----------
???????:<}/nzJQOwqdbkhao***####**o LUcx|[<;????????????????
]]]]]]]]][[[ !{xu; o#MW&8%BB@@@@@ -ct[l ]]]]]]]]]]]??-
U[[[[[[[}}}}}}}}} ;1X] $$$$$$$$$$ cx[" [[[[[[[[]]]??
UUJJJCCCLLL{{{{{{{{{{ :|QZzffB$$$$$$ |Qu? {{{{{{}}}[[]]??-
YUUJJJCCCLLLQQ000OOO111111111 ,l!!; 111111111111{{}}[[]]??-
YUUJJJCCCLLLQQQ00OOOZZZmmmwww(((((((((((((((((((()))))))))))))11{{ i]??-
YYUUUJJCCCLLL ?fuv| ZZZmmmwwwqqqpppd||||||||||||||||||((())11{ i++i;??--
YYYUUUJJJ i Cmmwwwqqqppppdddbbbbk///////||(())11 }czfYuf{_--
XYYUUU Wwwwqqqpppddddbbbbkkkk/||(())) |j :zr)--
XXYYY; $$wqqqqpppddddbbbbk/|||(()) ^X Jcf-
XXXY $$$$xwqqqppppddddbbb/||(()) v LX-_
zXX! $$$$$$$nqqqqppppdddbb||(()) q mQX-
zzX> $$$$$$$$$$$$qqqqppppddd|(()) k dmL-_
zzl $$$$$$$$$$$$$$wqqqqppppd((() o W*kqOJ__
czz? $$$$$$$$$$$$$$$$$ wqqqqpp|(() O $$BadmQ__
ccc!1x $$$$$$$$ wwqqqq(() {$$$$$$$Babw0___
vcc<)xXQm W%@$$$$$$ mwwwwq()) %$$$$$@%W#adwQ___
vvcc>1rzCZqkoM&B$$ bmmwww)) )o$$$$B&MokpZL-__+
uvvvcc]tuUQmpkoM Zmmmm)1 J- &MohdmQU-__++
uuvvvcc{jvUQmp ZZZm)11 J: kpmQUc-__;
nuuuvvvcc}fuYL nOOZZ11 /| .0CXu}-_
nuuvvvccc-)jv !00OOO11{ ;/zvzvxt1--
vvvcccz+{ }QQ000O1{{ !~+~>?-
ccczz:<] : LQQQQ00{{}}[ ]??
zzzzXX ";I;" JCCCLLLLQQQ{}}[[]]]?
zzXXXYYYUUUUJJJCCCCLLL{}}[[]]]
XXYYYYUUUJJJJCCCC}}[[]]
YYYUUUUJJJJC}[[]
YUUUUJJ[[
UU
Под катом построчный разбор запроса. Как обычно, достаточно знания основ SQL и школьной математики.
Читать полностью »