Аналогичный метод работает по модулю р за время 0(pN). [D. J. Bernstein, в печати.]

27. Из {W{qz) - W{z))V{z) = W{z){V{qz) - V{z)) получаем рекуррентную формулу Wn = ELi VkWn-kiq"" - g"-*)/(g - 1). [J. Difference Eqs. and Applies. 1 (1995), 57-60.]

28. Вначале заметим, что 5{U{z)V{z)) = {5U{z))V{z) + U{z){5V{z)), так как t{mn) = t{m) + t{n). Кроме того, индукцией по n получаем d{V{z)") = пУ(г)~(5У(г) для всех п > 0. Это равенство необходимо, чтобы показать, что Se = n>oS{V{zY/n\) = е*(5У(г). Заменив в данном равенстве V{z) на lnV{z), получаем V{z)SlnV{z) = SV{z), поэтому S{V{zy) = гe°"f") = e°"f(5(QlnK(г)) = aViz)"- для всех комплексных чисел а.

Следовательно, требуемое рекуррентное соотношение имеет вид

(a) Wi = 1, И/„ = Ed\. d>i((« + md}/t{n) - l)VaWn/d ;

(b) Wi = l,Wn = j:d\n,d>Md)/t{n))VdWn/a ;

(c) Wx =0,Wn = Vn+ Zd\n,a>i(4d)/tin) - mWn/d

[Cm. H. W. Gould, AMM 81 (1974), 3-14. Данная формула справедлива, когда t - любая функция, такая, что t{m) + t{n) = t{mn) и t{n) = О тогда и только тогда, когда п = 1, но в предположении, что t не раскладывается на простые множители. Этот метод можно применять и для степенных рядов с произвольным множеством переменных. Тогда t - общая степень члена ряда.]

ПРИЛОЖЕНИЕ А

ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ

Таблица 1

ВЕЛИЧИНЫ, ЧАСТО ИСПОЛЬЗУЕМЫЕ В СТАНДАРТНЫХ ПОДПРОГРАММАХ И ПРИ АНАЛИЗЕ КОМПЬЮТЕРНЫХ ПРОГРАММ (40 ДЕСЯТИЧНЫХ ЗНАКОВ)

ч/2 = 1.41421 35623 73095 04880 16887 24209 69807 85697-ч/3 = 1.73205 08075 68877 29352 74463 41505 87236 694284-ч/5 = 2.23606 79774 99789 69640 91736 68731 27623 544064-VTO = 3.16227 76601 68379 33199 88935 44432 71853 37196--= 1.25992 10498 94873 16476 72106 07278 22835 05703--J/3 = 1.44224 95703 07408 38232 16383 10780 10958 83919- = 1.18920 71150 02721 06671 74999 70560 47591 52930-1п2 = 0.69314 71805 59945 30941 72321 21458 17656 807554-1пЗ = 1.09861 22886 68109 69139 52452 36922 52570 46475-1п 10 = 2.30258 50929 94045 68401 79914 54684 36420 760114-1/1п2 = 1.44269 50408 88963 40735 99246 81001 89213 742664-1/1п10 = 0.43429 44819 03251 82765 11289 18916 60508 22944-л- = 3.14159 26535 89793 23846 26433 83279 50288 41972-1° = 7Г/180 = 0.01745 32925 19943 29576 92369 07684 88612 713444-1/7Г = 0.31830 98861 83790 67153 77675 26745 02872 406894-7г = 9.86960 44010 89358 61883 44909 99876 15113 53137-Г(1/2) = 1.77245 38509 05516 02729 81674 83341 14518 279754-Г(1/3) = 2.67893 85347 07747 63365 56929 40974 67764 41287-Г(2/3) = 1.35411 79394 26400 41694 52880 28154 51378 551934-е = 2.71828 18284 59045 23536 02874 71352 66249 775724-1/е = 0.36787 94411 71442 32159 55237 70161 46086 744584-= 7.38905 60989 30650 22723 04274 60575 00781 318034-7 = 0.57721 56649 01532 86060 65120 90082 40243 10422-1п7г = 1,14472 98858 49400 17414 34273 51353 05871 16473-ф = 1.61803 39887 49894 84820 45868 34365 63811 772034-е< = 1,78107 24179 90197 98523 65041 03107 17954 916964-е"* = 2,19328 00507 38015 45655 97696 59278 73822 346164-sinl = 0,84147 09848 07896 50665 25023 21630 29899 96226-COS 1 = 0,54030 23058 68139 71740 09366 07442 97660 373234--С(2) = 0,93754 82543 15843 75370 25740 94567 86497 78979-С(3) = 1,20205 69031 59594 28539 97381 61511 44999 07650-1пф = 0,48121 18250 59603 44749 77589 13424 36842 31352-1/1п= 2,07808 69212 35027 53760 13226 06117 79576 77422--1п1п2 = 0,36651 29205 81664 32701 24391 58232 66946 94543-

Таблица 2

ВЕЛИЧИНЫ, ЧАСТО ИСПОЛЬЗУЕМЫЕ В СТАНДАРТНЫХ ПОДПРОГРАММАХ И ПРИ АНАЛИЗЕ КОМПЬЮТЕРНЫХ ПРОГРАММ (45 ВОСЬМЕРИЧНЫХ ЗНАКОВ)

Величины, расположенные слева от знака "=", заданы в десятичной системе счисления

0.1 0.01 0.001 0.0001 0.00001 : 0.000001 0.0000001 : 0.00000001 : 0.000000001 0.0000000001 : /2:

л/5:

\/Т0: 1п2 :

1пЗ = In 10 = 1/1п2 = 1/1п 10 =

к --

1° = V180 =

%/ = Г(1/2) = Г(1/3) = Г(2/3) = е = 1/е = е--

7 = In л- =

Ф--е = е-/* = sin 1 = cosl = -С(2) =

С(з) =

1пф = 1/1пф = -In In 2 =

: 0.063Ц 63Ц6 ЗЦбЗ Ц631 463Ц 63Ц6 ЗЦ63 Ц631 46315-

: 0.00507 53412 11210 24365 60501 53412 11210 24365 60510-

0.00040 61115 64510 65116 16355 44264 16254 02030 44612+

: 0.00003 21556 13530 ЩЦ 54512 15110 33021 15002 35223-

0.00000 24161 32610 10664 36041 06011 11401 56063 34411-

0.00000 02061 51364 05536 66151 55323 01146 44470 26033+ - 0.00000 00153 21145 15214 53644 12141 12312 20354 02151+ 0.00000 00012 51143 56106 04303 41314 11341 01512 63321+ 0.00000 00001 04560 21640 46655 12262 11426 40124 21142+ 0.00000 00000 06616 33166 35361 55653 31265 34 64 2 01621- 1.32404 14631 11161 46220 42621 66115 46125 12515 11435+ : 1.56663 65641 30231 25163 54453 50265 60361 34013 42223- 2.11061 36334 51122 41602 57411 63003 00563 55620 32021-: 3.12305 40126 64555 22444 02242 51101 4Ц66 33115 22532+ 1.20505 05146 15345 05342 10156 65334 25514 Щ15 03024+ 1.34233 50444 75 13134 61363 76133 05334 31141 60121-I.I4O61 14050 61556 12455 12152 644ЗО 60211 02155 13136+ 0.54211 02115 15011 13632 51111 01316 30001 11366 53640+ 1.06231 24152 55006 05221 З244О 63065 25012 35514 55337+ 2.23213 06135 52524 25405 56512 66542 56026 46050 50105+ 1.34252 16624 53405 11021 35150 31166 4о644 35115 04353+ 0.33626 15425 11562 4I6I4 52325 33525 21655 14156 06220-3.11031 55242 10264 30215 14230 63050 56006 10163 21122+ 0.01013 12152 11224 72344 25603 54216 63351 22056 11544+ 0.24216 30155 62344 20251 23160 41251 50165 15156 10061-11.61511 14461 62135 11322 25561 15466 30021 40654 З41ОЗ-1.61331 61106 64136 6524 1 41035 40510 15213 З441О 11162-2.53341 35234 51013 61316 13106 41644 54653 00106 66046-1.26523 51112 14154 14312 54512 31655 60126 23231 02452+ 2.55160 52130 50535 51246 52113 42542 OO41I 12363 61661+ 0.21426 53066 13161 46161 52126 15436 02440 52311 03355+ 1.30114 45615 23355 33460 63501 35040 32664 Z5356 50211+ 0.44142 1411061666 06112 23215 14316 01002 51313 25521-1.11206 40443 41503 36413 65314 52661 52410 31511 46051+ 1.41433 51156 21151 23101 21634 II4OI 40211 66110 15010+ 1.61112 13452 61152 65161 22411 36553 53321 11554 21260+ 2.14215 31512 16162 52310 35530 11342 53525 44301 02111-0.65665 244З6 04414 13402 03061 23644 ii612 01414 14505-0.42450 50031 З24О6 42111 01022 14666 21320 10615 12321+ 0.14001 45144 53253 42362 42101 23350 50014 46IOO 21106+ 1.14135 00023 6OOI4 20410 15613 42561 31115 10111 O66I4+ 0.36630 26256 61213 01145 13700 4IOO4 52264 30100 4О646+ 2.O41I6 60111 11144 41512 114З6 16515 00355 4З6ЗО 40651+ 0.21351 11233 61265 63650 II4OI 56631 26334 31455 51005-