roots

Jason Moxham J.L.Moxham@maths.soton.ac.uk
Wed, 23 Oct 2002 17:08:08 +0100


--------------Boundary-00=_KHZFUCTL6YN2GM82RITI
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

some preliminary timings
speedups on linux athlon against GMP4.1 mpz_root

without rem
=09roots
bits=09cbrt=095th=0922nd
100=090.082=090.075=090.039
200=090.132=090.106=090.085
500=090.237=090.219=090.162
1000=090.446=090.416=090.387
2000=090.952=090.931=090.857
5000=092.943=093.322=093.345
10000=095.566=097.046=099.260
20000=098.319=0912.13=0925.05
50000=0911.54=0918.58=0958.40
100000=0913.13=0920.83=0982.69
200000=0914.53=0923.56=0999.92
500000=0914.83=0924.66=09big
1e6=0915.86=0926.16=09big
2e6=0917.87=0923.49=09big
5e6=0918.19=0927.79=09big
1e7=0922.25=0928.51=09big

with rem

bits=09cbrt=095th=0922nd
100=090.085=090.074=090.039
200=090.123=090.107=090.087
500=090.234=090.218=090.164
1000=090.441=090.403=090.378
2000=090.911=090.877=090.816
5000=092.514=092.717=092.768
10000=094.276=094.901=096.104
20000=095.900=097.171=0911.27
50000=097.754=099.602=0917.04
100000=098.749=0910.51=0919.91
200000=099.572=0911.57=0921.87
500000=099.827=0912.20=0922.91
1e6=0910.77=0912.58=0925.74
2e6=0912.01=0912.55=09big
5e6=0913.61=0914.49=09big
1e7=0915.29=0915.52=09big

form the data above you can see that calulating the remander slows things=
 down=20
by a large factor

jason

--------------Boundary-00=_KHZFUCTL6YN2GM82RITI
Content-Type: application/x-tbz;
  name="root.tar.bz2"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="root.tar.bz2"

QlpoOTFBWSZTWYgNDL4ADy9/jfywAIB7f///k6vbz/////oBAIAhEAAACGAW/vnO+9A7w9okZUih
Pedp5QvM2Nnru+95r3Njb3ILq5fH3OvQ9NNOBNAYg1VHVOSVmdOaEiRNACGiYFU/T1NNFPao0fpR
gg9IZGgB+pNDR6j0gaaBAmpopsRT1NPTU9QeUANHqNBoANAAAAGIlQ2k9INGhkaDQNDIGIAGmgAN
AGCBJpJFGlNlNNNPUMRk0GjQAAAaAAGgAARKUCbKam00JtBqNqPSaMJ6gAAGjIA0A0yNBEkTQgRp
oJtQZDKR4o9Ue1QPUempoeo9QNPUNPUAD3rzenf4qOtruOOdcbayjJATgqAVtDFs49gsvlyLL70d
tXxixUv5eV8dua4WbVfQpIKLEQoaZJEVCJGbR/5+HAEi8NDdmb91t7js7Ky4im0sHYLU1jtjbLxS
D4zsoZ3gi82WV8GGDeIKyZrfY+MwRP5DL4gbKuuwrai4Bwu5OYFE8RQEbQj76W49wMZEH3g7RNeP
lApirHZlEbWqQ5FZOxm+Pljms9ZzW15C3NOZO7lhFOz1OUD6wkDZCJIIyCZhcilyK8cUbEVeZiqa
EoxYLEtlQGAoVWwTv4kCwYRCWIJlk8NNt7UU0RghuYzpahpIs0wiznQkbTGRQt2MhkxaMaIqW4ix
SC6dIGkh3WsWPM2Tdi1OnaKO9qXVhiIpGMRSqCMSYUlyKIxDPM9qUZM08+j1XRDqtSNxcHQd7b1d
FX3bU6BPlRLy0xTpVTYuOnQLoOcA4MX1mQXL8YGRIyECc8Y5E9VvxsCb5CqMCmyAaivkvwRBD8lg
KoGH4wUX40UACfGgpAuRBoiodEAKCBnFoiIMIBIqQiIXgsiBqgYdeiPLWbkTOiF6EhH1IDT+wxvd
tITG39nuiQIJPopOgHDu/rH8VFRUAKrpCstgrE4s2Kj4s8m4UAY4O3P58IrjZb+mYtKkXZt11BKb
x2KPlSLEGQ0iqZC0JXGxt3KwsICVs9sIvL23RsMxQpGF7wogtq4RggmJjEyY8IbsGrC2Csmx4scy
HIFEPCq5FaVbhrTUNWovltGCk6tV3LSVYGQwSA4rrqFOXhEJMscEZpglhUEAjrsxffUGBhQxxzHQ
tD1cqJeGpXJCXQ5FydqFhEsPrRrXh8eNqVe4tL7vsDUbQrvi0UwrOSvFvF1F9Qu0qPB8RVc23oK8
XMVPXjPfGx+h8OYvui1AjxH3kWVSO4DyrqID9+zKoo5EI0tFfVTpDj7dcI6p2dGL/z5aJap9dgIQ
Y5a+JhyG9YlqSWqU5NwJ5qtHWBfFb2eZZiO7hxJ3B31ll839Mmc+7I96aoOzzI3uG4uTJN3Shwbm
+wZZhVzJ9vwLaI4YPQkM6BCVQnVlBLp3ae6pdKBzsCYDAYNi6g4L8TE62VUH9wlHOpF9Plas1bMq
LJQG3LMWiL9YnItwuBpOEuZ1/HYc9UpC4QgUpQUrSR2NDSBGmOhYCaBAyETCgEyim5IqYACJYgXw
WN/RJkGEUWMYzBBtIyOpX2Y5hda8jZgaa+y3hWfspWEgaTFb79E6lExlu3ya31LCWRiAZW4nXcCC
XGgIkS0hCkqB1WTtTr1zlxw58CgKi9Nvuyrpp7IC8eJoGC5plSF512b9ufeaCGgGkKWlxDHcZ4w9
tDQQ1iF7NAyAjSdOc8tKSqJRERdWCYNtvVrgqrux1XWgFCyxFlobCRy7MapgDKOOIwv7PTpWVCGX
kGszSC+W8DtGGzx0AmdR4GDpxoDdYEIvcrkgH+xDXMn7xk68IwnEoqgMGKDEgMiAICoJGKiMSDOC
IgKoSEYihUNzFIx75P4KB6sUeUHoYl4GpAUK4hVFukE7MhYoN2Lz4g0iuCuulkSmIsypv+am96b6
ShDSBrpSDp9WCyJprS1B55c0OZD1Q+nstJPje21qoOEIkBQQoAMDtFu/VOyN44565WDztFGVhEXQ
JDoccOIdqXg33uBYW6vZmIAIXLX692eHbKBNA4Jvxd9yPttR1TOKZ/re9u6B0fXRUtpWANEO1N1E
DhwsL6zKK7RCYFtgboQ8Dz7dsgPSKntwok05gQ1UG82fLKgKaEQQ+/mbv6KxFeRQrTpdx00pyudw
0jE+e9qzxl3iNWEEEW7iuTy92RWOXa+N0M2u6j8JCgih2VevJCsVg5FNKe9WAZhly6MgvvhfI70d
y01Gg5eYYTpMo7ubYrQqdO61jh6+7xZ4eGPi+5H4PF5WFTbFErhEvh9MJRpvK6d88HrIg4Dhjfof
GQt6dKQbnMGEShk38HCnSOutRtsL6zkYBSoqjzYoqKIOYzku4ECg0FfBbWNFK1A6rCb5p0CBr3Dh
slp0uFVzfrZZohEgNPmUtWShTbTK1FinJpDIzZsiCyW0IHm9Lryrj6+QbAgMYyJGARhF9MEuGlrY
YM34jLZbTfdGrsGWTzz19alTHUtkGLrZFpKCTLZESG2SvyL7ahG14HZo5zubYOYwzNOUjXc6ygTC
ZN4RGmy2kIY4cemwyk1BuznkxBZQMi1FDCQFkibSMa1hGljTYhnluL0yapEkayxbMlGumDLGK7gX
w6+di3qGvr00daoa1SjqaHusgy5kbsN8VCFi1mxJYhRhDBg2NaG2Bo0b7G4bm+aNN1qBubmsFEQY
wTDRUYGDIxg0EfhCQDkMQPIeYQLzp/b4+z3/b/769ezmfOeMC7/CFwpEmU9kVCqgH9FtltdBQKQH
ZWpES0u1HlYlxMVaqmkqJerM8y5LKgDkcATZPCVAuzFQDlqI1jMLaDhekRnA7oCCTBYdT1DuJPgR
pYKp8tL2OHEeiRK9knKT0hwXTLnGt4yD2j3+z2Z3EDnJ+qsYzR1yKUDIgfdanPReItoJRLRMAtix
7Cw+yVEEwEA4jdkHZTCXDOzMzgm+J1HJjkWrFpD9ilodi9W/bWVtrfKiqGFF8LawdKHF/6z48QM/
Ml04lVhSH5fi0OeK9RkjNyXqQ63A2P2sgYmDQIIpuyNnwFKCK5LR9065dTVhvt3OGxDaBvCghQvr
kiipJlKSYCPHxDGyFgIQhHSXuRoMgFygCY5Poy5byowXad4SY2RuFxew4vjLhvrUkNFVpJ4SIJkU
hZ8kqSXlMvr/DOCfShKV6Wkx5VS3bW8wCbCGbdAzyt15Y4y416Qr8ExcnkKUb9QuBxnFapKowJQZ
BFN0wwUubmta2cU8dm3GaMBMSwsYjaXzYmS3vQQKqMNIFhQ7HXso5UMdDg7wBv4tAaEYCoILhVXe
wPKisqTdnJOgLFkd0pXeCjaRC+bM96SDWcNduqcpcdcbIv9wsqj+MT7PP0NCeOUEig0oGQNiRb2i
4FZLt8tV/4OdK46btdYgkONUe6BNKcLnjURQAch/rdUZK4yTZdjdQTdQAZCWeBrW2xxka3KI/Ndq
tVxI2Kq84sQlbIlxJ2FGDoiuqIyIzGpuoUkWsLBRS9ceuEvGr6LIPG2WOSSIJk4CK+XuzrA1WhzS
Vyiwr4RlcGyrZgVRFVAHV5WxvSBjHTAEYm7NXCqigpdEE8nRxc6F9gVarBMalevV59XxJ/16eIBQ
YXrOrzPfZ3E2w23Kqa7yNJxqxxCoO8J1/CzcooowLWhJttAL9R9NRI4PF3sPhYI+h1vJCbMKgTXy
03FYdB0JuyBiTkEUOrRQafZpV7oNvwNdp/T+GWFHZtJw32VP0VcPxfOfsvr5YMmOwHU+3wEtFOzT
Um9uL+SPygaFV8ygwQxXUNIawtGXUwwxADIgTp6FtuNx1sNLsDgKilQBX6Bst7HdrdS2JmN+LUwt
XqzhCWXGogz9QMMQ5AcSlDjxcqm/yeYtyCab5y8Nd5SriUlkYwGcuU6WMkYSBRRZnz62dS6d/ev3
kbkYCRok68mgTsOwgi7QiBl2WASsFP7Y7zOw6/u1uxUDBi+X6BzKkoVpioXICZWxKkolk7VMiFB9
Ag5iBQUIObIwHBGgWCEYSRnsnbuQYRQgcSNa7f2/HfWL3MLNty9/2lFOoQOK/I8x+0Yv+jYM7hn7
v1gRlwOh+1NNTzPbvXh7Upi/kKfP19oqF9SwHYtgQ0HghAPuX7PxUAwXftHX6Dl1Gb4dp/8akSEX
R9LEgVSHOBP70vYCxEPFhBgG8vTgJ5oS0TIfvA9KfgZn60MGT6Cjwi6wwe0TaCRTeZjk9Y+mpsPA
bX9+leIdQv1BiIuDVV0VkRurYgVjMCtpLQFocigWJE+9hGn7Ad67uCgE7tnlGhH4Ae2/SUbscUUw
SqoJw0MlyN9GtjSELymTH63PonJK1YAYA08Ulge8LjuWg0IMAsE2lksdLu5jvGmgiMS/h5ZCWCsv
dknC9vfjrxmRbST5/P9+qqi1+B3hmiGpwMlEh0QjTeb5lgZA66GkNZmoAGQNFGBpFu+lodvZr9EO
ldmamY2E29UN1kWlB5o8RMeXcqFIHiinrnAX0h4/74Qyf8DBlCmHuM2QuSDYqE82QRkRlCFgIiSC
hkogoIFjARBEhYMknGavaTxBkl3BLkEgVF50ptSQC0PMcxeQlhLMtwlrMBJUixZbwMh2wSyy8BgZ
KkoYpEwQUYzaKmz0DzknSej4MlG02JqALJDDSUw407XKS/y8jW8/lE4tw71Heom17X2/pccGQjdu
NxKsyx4AFIHuRD45lGOy9EQsO2QXrV60XGBkWDEhJIRHPxbmBHMUTWDb6oBjvpCRjJJIczJD5K4D
yghzVkE/Oa58HIOgk4juEeq7qQ72tjmmyBJcFNow7jiYBDiJge4nZD6L35GVBcJLWY1bWjpsNF8q
iQhDyIJCW5PjbFuo5vrhRIBTWpiJJkNhfIDJAt0miIZwDPpfUDfCPkncCBcc1Ms7EO1GyiZX9I7x
M1daOFyJ36HcczkPAb8I90Pue4OseCwKSAwbnQD+ZDoQAEL1Jw+i7ooiixewd7ykMhOq7ILJNbFh
ckqlVP55y6dcVQeDmrFBUEd9oTGEYGknHsFXLRQRgu6bO+kagzWVKxa1oalg7vBkAIJ0LwFiTpIp
Q9pCHVTX/qJRfZwIM5BcczNRMsoTi4R1Q7wSKw+JoaAQC1wgbFE13ibUUytxlKpsCi3550yEttdi
rnogxaEgVQLoWAChgPrOfNkqEruu+pET3FYa1VkdxF3R61YVpqjF2kuDJCqFEBqUcVxQc+MWgM6A
o96F0HBRmKHvsncl4aobN3SMCW0O8LQYAUIQIcKK37NhLB8oBONXHQgIBKRsbAunU16B5Pz3BYC9
thhSo1wJiY5HZ2jYawq1ShIEDPFFfWeewIHnGiJCqJVMJgV6/IU8VgQj9nqKU5DcCFqvEoHZTazk
6ayMDQYVIbCURzNgaB3DRwCGo6r7XRHsB8ikHZuhckgN94AsyYoWHAbbNm/aX1lSomregjaHagdJ
2IV2b1APMgJM1ovPNPUNi1tsC5ynEyUhsbG7kLEx7hcEGiFLixsbGliESCJ1bADOQCCQgWQrAFDS
fOZXXrPyxqMXSmIOZS+Z8h70wmyjEAiCAdZk+9PxTQMiMnSJ0TjBRFGCZ4J1Oabc5iAOoFnEDsvZ
aKbJPAHbKSwmai268CamPHF3VQC93LJ5YougwQqNENNWYOf0OhotoBd1LVCZVZzHMLF8lgKMhRhS
kpU7NR8jRm0prYtKOmgZRoDcRbKYeMyGGcOVUnPNUJ0uE27wppWO5OKgFkMETpB6RAgFzU5SIgKd
7S2xGorGJSy2MYyFgJGoBwMQFYoM+ccsqhC+QzuVENCjojnMuujZL2CLMzqhNcWkAauQ/NEMYxpx
Bkb6hYG+b+1QbqGRHkoBsAIdrUEJFT6kToIJcEwe1Ngc4j4zwnja9n1OYofyD7jvnOCtQcQ/5bQ+
R5luqWnDJmm6Im8RpJBQIXC4gRrsfQjbvEdvE2DmyAFyjAnldyRg/pCmmC9ZVMOwoKIfsM0E3fqy
nW4XiHy1HkpcBUlYI6ImnT20sSHhBTcFjGYDEKXcyUyG5lToFCiJkFFdATeHAZRFgLukpAkCRTLB
NEyEJiOWED/xdyRThQkIgNDL4A==

--------------Boundary-00=_KHZFUCTL6YN2GM82RITI--