fft.ps

Data Structure Ebook

1730 y Fn(In)13 b(section)i(12,)e(w)o(e)h(used)g(the)h
Fg(c)n(o)n(e\016cient)f(form)f Fn(to)h(represen)o(t)i(the)e(p)q
(olynomials.)h(There)262 1780 y(is)f(an)h(alternativ)o(e)g(w)o(a)o(y)f
(to)h(represen)o(t)j(p)q(olynomial)o(s,)13 b(using)h(the)i
Fg(p)n(oint-value)g(r)n(epr)n(esen-)262 1830 y(tation)p
Fn(.)h(A)c(p)q(olynomial)d(of)i(degree)i Fm(n)8 b Ff(\000)f
Fn(1)13 b(can)g(b)q(e)g(represen)o(ted)j(b)o(y)d Fm(n)f
Fn(p)q(oin)o(t-v)n(alue)g(pairs:)657 1929 y Ff(f)p Fn(\()p
Fm(x)718 1935 y Fj(0)736 1929 y Fm(;)7 b(y)775 1935 y
Fj(0)794 1929 y Fn(\))p Fm(;)g Fn(\()p Fm(x)869 1935
y Fj(1)887 1929 y Fm(;)g(y)926 1935 y Fj(1)944 1929 y
Fn(\))p Fm(;)g(:)g(:)g(:)e(;)i Fn(\()p Fm(x)1093 1935
y Fl(n)p Fk(\000)p Fj(1)1157 1929 y Fm(;)g(y)1196 1935
y Fl(n)p Fk(\000)p Fj(1)1261 1929 y Fn(\))p Ff(g)262
2021 y Fn(where)324 2104 y Ff(\017)20 b Fn(All)13 b(the)i
Fm(x)529 2110 y Fl(k)563 2104 y Fn(are)f(distinct)324
2187 y Ff(\017)20 b Fm(y)385 2193 y Fl(k)418 2187 y Fn(=)11
b Fm(A)p Fn(\()p Fm(x)532 2193 y Fl(k)553 2187 y Fn(\))262
2303 y Fh(12.2)55 b(Uniqueness)18 b(Theorem)262 2380
y Fn(F)m(or)13 b(an)o(y)g(set)i(of)e Fm(n)h Fn(p)q(oin)o(ts,)g(there)h
(is)e(a)h(unique)g(p)q(olynomial.)262 2429 y(\(F)m(or)f(a)h(pro)q(of,)f
Fg(se)n(e)h Fn(Cormen)f Fg(et)h(al.)p Fn(\).)967 2574
y(1)p eop
%%Page: 2 2
2 1 bop 262 307 a Fh(12.3)55 b(Op)r(erations)18 b(in)g(the)h(P)n(oin)n
(t-V)-5 b(alue)19 b(Represen)n(tation)262 384 y Fn(If)13
b(w)o(e)h(ha)o(v)o(e)g(t)o(w)o(o)f(p)q(olynomials,)e
Fm(A)j Fn(and)f Fm(B)r Fn(:)586 471 y Fm(A)p Fn(\()p
Fm(x)p Fn(\))e(=)h Ff(f)p Fn(\()p Fm(x)789 477 y Fj(0)807
471 y Fm(;)7 b(y)846 477 y Fj(0)865 471 y Fn(\))p Fm(;)g
Fn(\()p Fm(x)940 477 y Fj(1)958 471 y Fm(;)g(y)997 477
y Fj(1)1015 471 y Fn(\))p Fm(;)g(:)g(:)g(:)e(;)i Fn(\()p
Fm(x)1164 477 y Fl(n)p Fk(\000)p Fj(1)1229 471 y Fm(;)g(y)1268
477 y Fl(n)p Fk(\000)p Fj(1)1333 471 y Fn(\))p Ff(g)262
550 y Fn(and)584 600 y Fm(B)r Fn(\()p Fm(x)p Fn(\))13
b(=)e Ff(f)p Fn(\()p Fm(x)790 606 y Fj(0)809 600 y Fm(;)c(y)849
583 y Fk(0)848 610 y Fj(0)866 600 y Fn(\))p Fm(;)g Fn(\()p
Fm(x)941 606 y Fj(1)959 600 y Fm(;)g(y)999 583 y Fk(0)998
610 y Fj(1)1017 600 y Fn(\))p Fm(;)g(:)g(:)g(:)e(;)i
Fn(\()p Fm(x)1166 606 y Fl(n)p Fk(\000)p Fj(1)1230 600
y Fm(;)g(y)1270 583 y Fk(0)1269 610 y Fl(n)p Fk(\000)p
Fj(1)1334 600 y Fn(\))p Ff(g)262 667 y Fn(where)15 b(all)d(the)j
Fm(x)535 673 y Fl(k)569 667 y Fn(are)f(the)g(same,)f(then)286
754 y Fm(C)s Fn(\()p Fm(x)p Fn(\))e(=)h Fm(A)p Fn(\()p
Fm(x)p Fn(\))d(+)h Fm(B)r Fn(\()p Fm(x)p Fn(\))i(=)g
Ff(f)p Fn(\()p Fm(x)774 760 y Fj(0)792 754 y Fm(;)7 b(y)831
760 y Fj(0)858 754 y Fn(+)j Fm(y)921 737 y Fk(0)920 764
y Fj(0)939 754 y Fn(\))p Fm(;)d Fn(\()p Fm(x)1014 760
y Fj(1)1032 754 y Fm(;)g(y)1071 760 y Fj(1)1099 754 y
Fn(+)i Fm(y)1161 737 y Fk(0)1160 764 y Fj(1)1179 754
y Fn(\))p Fm(;)e(:)g(:)g(:)e(;)i Fn(\()p Fm(x)1328 760
y Fl(n)p Fk(\000)p Fj(1)1392 754 y Fm(;)g(y)1431 760
y Fl(n)p Fk(\000)p Fj(1)1506 754 y Fn(+)i Fm(y)1568 737
y Fk(0)1567 764 y Fl(n)p Fk(\000)p Fj(1)1633 754 y Fn(\))p
Ff(g)262 833 y Fn(and)387 912 y Fm(C)s Fn(\()p Fm(x)p
Fn(\))i(=)h Fm(A)p Fn(\()p Fm(x)p Fn(\))633 902 y(_)618
912 y Fm(B)s Fn(\()p Fm(x)p Fn(\))f(=)h Ff(f)p Fn(\()p
Fm(x)824 918 y Fj(0)843 912 y Fm(;)7 b(y)882 918 y Fj(0)900
912 y Fm(y)921 895 y Fk(0)920 922 y Fj(0)939 912 y Fn(\))p
Fm(;)g Fn(\()p Fm(x)1014 918 y Fj(1)1032 912 y Fm(;)g(y)1071
918 y Fj(1)1089 912 y Fm(y)1110 895 y Fk(0)1109 922 y
Fj(1)1128 912 y Fn(\))p Fm(;)g(:)g(:)g(:)e(;)i Fn(\()p
Fm(x)1277 918 y Fl(n)p Fk(\000)p Fj(1)1342 912 y Fm(;)g(y)1381
918 y Fl(n)p Fk(\000)p Fj(1)1446 912 y Fm(y)1467 895
y Fk(0)1466 922 y Fl(n)p Fk(\000)p Fj(1)1531 912 y Fn(\))p
Ff(g)262 991 y Fn(giving)i(a)i(\002\()p Fm(n)p Fn(\))h(pro)q(cedure)h
(for)e(m)o(ultiplyi)o(ng)d(t)o(w)o(o)j(p)q(olynomials.)j(But)e(note)f
(that)h(w)o(e)f(no)o(w)262 1041 y(need)j(2)p Fm(n)g Fn(p)q(oin)o(ts)g
(in)f(our)h(represen)o(tations)i(of)d Fm(A)h Fn(and)g
Fm(B)r Fn(.)262 1091 y(Unfortunately)m(,)k(con)o(v)o(ersion)h(b)q(et)o
(w)o(een)h(co)q(e\016cien)o(t)f(and)f(p)q(oin)o(t-v)n(alue)g(represen)o
(tations)262 1141 y(requires)d(generating)f Fm(n)g Fn(or)g(2)p
Fm(n)g Fn(p)q(oin)o(ts.)k(Ev)n(aluating)13 b Fm(y)1142
1147 y Fl(k)1175 1141 y Fn(=)f Fm(A)p Fn(\()p Fm(x)1290
1147 y Fl(k)1310 1141 y Fn(\))i(requires)i(\002\()p Fm(n)p
Fn(\))e(op)q(er-)262 1190 y(ations)f(using)h(Horner's)g(rule,)g(so)g
(the)g(con)o(v)o(ersion)h(is)e(\002\()p Fm(n)1194 1175
y Fj(2)1213 1190 y Fn(\)!)262 1240 y(Ho)o(w)o(ev)o(er,)k(note)h(that)f
(w)o(e)h(can)f(c)o(ho)q(ose)h(an)o(y)e Fm(x)1017 1246
y Fl(k)1055 1240 y Fn(as)h(long)f(as)h(they)h(are)g(distinct.)28
b(If)16 b(w)o(e)262 1290 y(c)o(ho)q(ose)k(the)g Fm(n)g
Fg(c)n(omplex)g Fm(n)708 1275 y Fl(th)762 1290 y Fg(r)n(o)n(ots)f(of)h
(unity)p Fn(,)h(then)f(w)o(e)f(are)h(p)q(erforming)e(a)h(Discrete)262
1340 y(F)m(ourier)e(T)m(ransform.)26 b(As)18 b(w)o(e)f(will)f(sho)o(w,)
i(this)f(tak)o(es)h(\002\()p Fm(n)7 b Fn(log)g Fm(n)p
Fn(\))17 b(time.)27 b(The)18 b(rev)o(erse)262 1390 y(transformation)c
(\(from)g(p)q(oin)o(t-v)n(alue)h(to)h(co)q(e\016cien)o(t)h(represen)o
(tation\),)h(called)e Fg(interp)n(o-)262 1439 y(lation)p
Fn(,)d(is)h(also)f(a)g(F)m(ourier)h(T)m(ransform,)e(also)h(requiring)h
(\002\()p Fm(n)7 b Fn(log)f Fm(n)p Fn(\))14 b(time.)262
1489 y(This)f(leads)h(us)h(to)e(the)i(follo)o(wing)c(p)q(olynomial)g(m)
o(ultipli)o(cation)g(algorithm:)p 262 1503 1345 2 v 261
1603 2 100 v 286 1538 a(Augmen)o(t)h(p)q(olynomials)e
Fm(A)j Fn(and)g Fm(B)i Fn(b)o(y)e(adding)f Fm(n)h Fn(higher)g(order)h
(0)286 1588 y(co)q(e\016cien)o(ts)p 1373 1603 V 1445
1538 a(\002\()p Fm(n)p Fn(\))p 1605 1603 V 262 1604 1345
2 v 261 1804 2 200 v 286 1639 a Fg(Evaluate)286 1689
y Fn(Compute)i(p)q(oin)o(t-v)n(alue)g(represen)o(tation)i(of)e
Fm(A)p Fn(\()p Fm(x)p Fn(\))h(and)f Fm(B)r Fn(\()p Fm(x)p
Fn(\))i(b)o(y)286 1739 y(t)o(w)o(o)c(applications)f(of)g(the)h(FFT)286
1789 y Ff(\))g Fn(v)n(alues)f(at)h(eac)o(h)h(\(2)p Fm(n)p
Fn(\))688 1774 y Fl(th)735 1789 y Fn(ro)q(ot)f(of)g(unit)o(y)m(.)p
1373 1804 V 1399 1639 a(\002\()p Fm(n)7 b Fn(log)g Fm(n)p
Fn(\))p 1605 1804 V 262 1805 1345 2 v 261 1855 2 50 v
286 1840 a(P)o(oin)o(t-wise)14 b(m)o(ultiply)p 1373 1855
V 802 w(\002\()p Fm(n)p Fn(\))p 1605 1855 V 262 1857
1345 2 v 261 1956 2 100 v 286 1892 a Fg(Interp)n(olate)286
1942 y Fn(Create)h(co)q(e\016cien)o(t)g(represen)o(tation)g(b)o(y)f
(application)f(of)g(FFT)p 1373 1956 V 1399 1892 a(\002\()p
Fm(n)7 b Fn(log)g Fm(n)p Fn(\))p 1605 1956 V 262 1958
1345 2 v 261 2008 2 50 v 286 1993 a(T)m(otal)p 1373 2008
V 1016 w(\002\()p Fm(n)g Fn(log)g Fm(n)p Fn(\))p 1605
2008 V 262 2010 1345 2 v 262 2104 a Fh(12.4)55 b(Complex)17
b(Ro)r(ots)h(of)h(Unit)n(y)262 2181 y Fn(The)14 b(complex)e
Fm(n)534 2166 y Fl(th)582 2181 y Fn(ro)q(ot)i(of)f(unit)o(y)m(,)g
Fm(!)q Fn(,)h(is)f(de\014ned)i(b)o(y:)915 2260 y Fm(!)942
2243 y Fl(n)976 2260 y Fn(=)d(1)262 2339 y(There)j(are)f(exactly)g
Fm(n)g Fn(suc)o(h)g(ro)q(ots:)520 2437 y Fm(e)544 2409
y Fe(2)p Fd(\031)q(ik)p 544 2414 60 2 v 565 2430 a(n)622
2437 y Fn(=)e(cos)733 2409 y(2)p Fm(\031)q(k)p 733 2428
69 2 v 755 2466 a(n)816 2437 y Fn(+)e Fm(i)d Fn(sin)942
2409 y(2)p Fm(\031)q(k)p 942 2428 V 964 2466 a(n)1030
2437 y(f)t(or)15 b(k)e Fn(=)f(0)p Fm(;)7 b Fn(1)p Fm(;)g(:)g(:)g(:)s(;)
g(n)i Ff(\000)g Fn(1)967 2574 y(2)p eop
%%Page: 3 3
3 2 bop 262 307 a Fn(The)14 b Fg(princip)n(al)g Fm(n)544
292 y Fl(th)593 307 y Fg(r)n(o)n(ot)g(of)h(unity)f Fn(is)888
403 y Fm(!)914 409 y Fl(n)948 403 y Fn(=)e Fm(e)1016
375 y Fe(2)p Fd(\031)q(i)p 1017 380 44 2 v 1029 396 a(n)262
494 y Fn(The)i(other)g(ro)q(ots)h(are)828 544 y Fm(!)855
527 y Fj(2)854 554 y Fl(n)876 544 y Fm(;)7 b(!)922 527
y Fj(3)921 554 y Fl(n)943 544 y Fm(;)g(:)g(:)g(:)e(;)i(!)1063
527 y Fl(n)p Fk(\000)p Fj(1)1062 554 y Fl(n)262 660 y
Fh(12.5)55 b(Prop)r(erties)17 b(of)i Fc(!)351 806 y Fn(Cancellation)404
856 y(lemma)691 736 y(F)m(or)13 b(an)o(y)g Fm(n)f Ff(\025)g
Fn(0)p Fm(;)7 b(k)k Ff(\025)h Fn(0)p Fm(;)7 b(d)k(>)g
Fn(0:)960 827 y Fm(!)987 810 y Fl(dk)986 837 y(dn)1037
827 y Fn(=)h Fm(!)1108 810 y Fl(k)1107 837 y(n)691 968
y Fn(F)m(or)h(an)o(y)g(ev)o(en)i Fm(n)c(>)h Fn(0:)912
1066 y Fm(!)944 1031 y Fd(n)p 944 1036 19 2 v 946 1052
a Fe(2)938 1071 y Fl(n)981 1066 y Fn(=)g Fm(!)1051 1072
y Fj(2)1081 1066 y Fn(=)g Ff(\000)p Fn(1)393 1278 y(Halving)404
1328 y(lemma)691 1208 y(If)j Fm(n)g Fn(is)h(ev)o(en,)g(the)h(squares)g
(of)e(the)h Fm(n)g Fn(com-)691 1257 y(plex)f Fm(n)806
1242 y Fl(th)856 1257 y Fn(ro)q(ots)g(of)g(unit)o(y)g(are)h(the)1271
1241 y Fl(n)p 1271 1248 21 2 v 1273 1272 a Fj(2)1312
1257 y Fn(com-)691 1307 y(plex)d(\()800 1291 y Fl(n)p
800 1298 V 802 1322 a Fj(2)826 1307 y Fn(\))842 1292
y Fl(th)890 1307 y Fn(ro)q(ots.)262 1489 y Fh(12.6)55
b(The)19 b(F)-5 b(ast)19 b(F)-5 b(ourier)18 b(T)-5 b(ransform)262
1566 y Fn(T)m(o)13 b(ev)n(aluate)g Fm(A)p Fn(\()p Fm(x)p
Fn(\),)h(w)o(e)g(divide)f(it)h(in)o(to)f(t)o(w)o(o)g(parts:)559
1657 y Fm(A)590 1640 y Fl(ev)q(en)662 1657 y Fn(\()p
Fm(x)p Fn(\))f(=)f Fm(a)795 1663 y Fj(0)823 1657 y Fn(+)f
Fm(a)887 1663 y Fj(2)905 1657 y Fm(x)f Fn(+)h Fm(a)1002
1663 y Fj(4)1020 1657 y Fm(x)1044 1640 y Fj(2)1072 1657
y Fn(+)f Fm(:)e(:)g(:)h Fn(+)h Fm(a)1234 1663 y Fl(n)p
Fk(\000)p Fj(2)1300 1657 y Fm(x)1329 1629 y Fd(n)p 1328
1634 19 2 v 1330 1650 a Fe(2)1351 1640 y Fk(\000)p Fj(1)262
1749 y Fn(and)568 1798 y Fm(A)599 1781 y Fl(odd)653 1798
y Fn(\()p Fm(x)p Fn(\))i(=)h Fm(a)786 1804 y Fj(1)814
1798 y Fn(+)d Fm(a)877 1804 y Fj(3)896 1798 y Fm(x)g
Fn(+)g Fm(a)992 1804 y Fj(5)1011 1798 y Fm(x)1035 1781
y Fj(2)1062 1798 y Fn(+)h Fm(:)d(:)g(:)h Fn(+)h Fm(a)1225
1804 y Fl(n)p Fk(\000)p Fj(1)1290 1798 y Fm(x)1319 1770
y Fd(n)p 1319 1775 V 1321 1791 a Fe(2)1342 1781 y Fk(\000)p
Fj(1)262 1873 y Fn(no)o(w)701 1923 y Fm(A)p Fn(\()p Fm(x)p
Fn(\))j(=)f Fm(A)874 1906 y Fl(ev)q(en)946 1923 y Fn(\()p
Fm(x)986 1906 y Fj(2)1005 1923 y Fn(\))e(+)h Fm(A)1103
1906 y Fl(odd)1156 1923 y Fn(\()p Fm(x)1196 1906 y Fj(2)1214
1923 y Fn(\))p Fm(x)262 1998 y Fn(So)j(ev)n(aluating)g
Fm(A)p Fn(\()p Fm(x)p Fn(\))h(at)794 2048 y Fm(!)821
2030 y Fj(0)820 2058 y Fl(n)843 2048 y Fm(;)7 b(!)889
2030 y Fj(1)888 2058 y Fl(n)909 2048 y Fm(;)g(!)955 2030
y Fj(2)954 2058 y Fl(n)976 2048 y Fm(;)g(:)g(:)g(:)e(;)i(!)1096
2030 y Fl(n)p Fk(\000)p Fj(1)1095 2058 y Fl(n)262 2122
y Fn(reduces)15 b(to)312 2205 y(1.)20 b(Ev)n(aluating)13
b Fm(A)606 2190 y Fl(ev)q(en)677 2205 y Fn(\()p Fm(x)p
Fn(\))h(and)g Fm(A)859 2190 y Fl(odd)912 2205 y Fn(\()p
Fm(x)p Fn(\))g(at)744 2297 y(\()p Fm(!)787 2279 y Fj(0)786
2307 y Fl(n)809 2297 y Fn(\))825 2279 y Fj(2)844 2297
y Fm(;)7 b Fn(\()p Fm(!)906 2279 y Fj(1)905 2307 y Fl(n)927
2297 y Fn(\))943 2279 y Fj(2)961 2297 y Fm(;)g Fn(\()p
Fm(!)1023 2279 y Fj(2)1022 2307 y Fl(n)1044 2297 y Fn(\))1060
2279 y Fj(2)1079 2297 y Fm(;)g(:)g(:)g(:)e(;)i Fn(\()p
Fm(!)1215 2279 y Fl(n)p Fk(\000)p Fj(1)1214 2307 y Fl(n)1280
2297 y Fn(\))1296 2279 y Fj(2)365 2388 y Fg(but)18 b
Fn(these)h(are)f(the)h(complex)d(\()884 2372 y Fl(n)p
884 2379 21 2 v 886 2402 a Fj(2)910 2388 y Fn(\))926
2373 y Fl(th)977 2388 y Fn(ro)q(ots)i(of)f(unit)o(y)h(and)f(there)i
(are)f(only)1617 2372 y Fl(n)p 1617 2379 V 1619 2402
a Fj(2)1660 2388 y Fn(of)365 2438 y(them.)967 2574 y(3)p
eop
%%Page: 4 4
4 3 bop 312 307 a Fn(2.)20 b(Com)o(bining)11 b(them.)262
387 y(So)k(w)o(e)h(ha)o(v)o(e)f(divided)g(our)h(\002\()p
Fm(n)778 372 y Fj(2)797 387 y Fn(\))f(ev)n(aluation)g(in)o(to)f(t)o(w)o
(o)h(sub-problems)g(of)g(size)1586 371 y Fl(n)p 1586
378 21 2 v 1588 401 a Fj(2)1611 387 y Fn(.)23 b(As)262
437 y(usual,)c(w)o(e)g(can)g(divide)f(the)i(problem)d(log)7
b Fm(n)19 b Fn(times,)f(giving)g(a)g(\002\()p Fm(n)7
b Fn(log)g Fm(n)p Fn(\))19 b(ev)n(aluation)262 487 y(algorithm.)262
536 y(Th)o(us)9 b(the)h(time)e(complexit)o(y)f(of)i(FFT)g(is)g(\002\()p
Fm(n)e Fn(log)g Fm(n)p Fn(\))j(and)f(w)o(e)g(ha)o(v)o(e)g(dev)o(elop)q
(ed)h(a)f(\002\()p Fm(n)e Fn(log)g Fm(n)p Fn(\))262 586
y(algorithm)k(for)i(m)o(ultiplying)e(p)q(olynomial)o(s.)262
702 y Fh(12.7)55 b(Recursiv)n(e)17 b(FFT)262 778 y Fn(A)c(recursiv)o(e)
j(FFT)e(algorithm)d(has)j(the)h(follo)o(wing)c(form:)724
863 y Fm(f)t(f)t(t)p Fn(\()p Fm(a;)c(n)p Fn(\))765 912
y Fm(if)19 b(n)12 b Fn(=)g(1)h Fm(then)h(r)q(etur)q(n)g(a)p
Fn(;)765 967 y Fm(!)791 973 y Fl(n)825 967 y Fn(=)e Fm(e)893
941 y Fe(2)p Fd(\031)q(i)p 893 946 44 2 v 906 962 a(n)765
1017 y Fm(!)h Fn(=)f(1)765 1067 y Fm(a)787 1052 y Fl(e)817
1067 y Fn(=)g(\()p Fm(a)899 1073 y Fj(0)917 1067 y Fm(;)7
b(a)958 1073 y Fj(2)976 1067 y Fm(;)g(a)1017 1073 y Fj(4)1035
1067 y Fm(;)g(:)g(:)g(:)e(;)i(a)1150 1073 y Fl(n)p Fk(\000)p
Fj(2)1215 1067 y Fn(\))765 1117 y Fm(a)787 1102 y Fl(o)817
1117 y Fn(=)12 b(\()p Fm(a)899 1123 y Fj(1)918 1117 y
Fm(;)7 b(a)959 1123 y Fj(3)977 1117 y Fm(;)g(a)1018 1123
y Fj(5)1036 1117 y Fm(;)g(:)g(:)g(:)e(;)i(a)1151 1123
y Fl(n)p Fk(\000)p Fj(1)1215 1117 y Fn(\))765 1167 y
Fm(y)786 1152 y Fl(e)817 1167 y Fn(=)k Fm(f)t(f)t(t)p
Fn(\()p Fm(a)961 1152 y Fl(e)981 1167 y Fm(;)1004 1150
y Fl(n)p 1004 1157 21 2 v 1006 1181 a Fj(2)1030 1167
y Fn(\))765 1217 y Fm(y)786 1201 y Fl(o)817 1217 y Fn(=)h
Fm(f)t(f)t(t)p Fn(\()p Fm(a)962 1201 y Fl(o)982 1217
y Fm(;)1006 1200 y Fl(n)p 1006 1207 V 1008 1231 a Fj(2)1031
1217 y Fn(\))765 1266 y Fm(f)t(or)k(k)c Fn(=)g(0)i Fm(to)1011
1250 y Fl(n)p 1011 1257 V 1013 1281 a Fj(2)1046 1266
y Ff(\000)9 b Fn(1)807 1316 y Fm(y)827 1322 y Fl(k)859
1316 y Fn(=)j Fm(y)924 1301 y Fl(e)923 1328 y(k)953 1316
y Fn(+)e Fm(!)q(y)1043 1301 y Fl(o)1042 1328 y(k)807
1366 y Fm(y)827 1372 y Fl(k)q Fj(+)876 1361 y Fd(n)p
876 1366 19 2 v 878 1382 a Fe(2)913 1366 y Fn(=)i Fm(y)978
1351 y Fl(e)977 1378 y(k)1007 1366 y Ff(\000)d Fm(!)q(y)1096
1351 y Fl(o)1095 1378 y(k)807 1417 y Fm(!)k Fn(=)f Fm(!)q(!)943
1423 y Fl(n)765 1467 y Fm(r)q(etur)q(n)i(y)262 1578 y