50:
depend on each other's results may run in parallel. Horner's method contains a series of multiplications and additions that each depend on the previous instruction and so cannot execute in parallel. Estrin's scheme is one method that attempts to overcome this serialization while still being reasonably close to optimal.
49:
for evaluation of polynomials is one of the most commonly used algorithms for this purpose, and unlike Estrin's scheme it is optimal in the sense that it minimizes the number of multiplications and additions required to evaluate an arbitrary polynomial. On a modern processor, instructions that do not
571:
squarings in line 3. In exchange for those extra squarings, all of the operations in each level of the scheme are independent and may be computed in parallel; the longest dependency path is
2084:
2064:
2024:
59:
2100:
248:
40:
557:
multiply-accumulate operations (the same as Horner's method) in line 1, and an additional
8:
2043:
46:
20:
2060:
251:
instruction on some architectures, an advantage that is shared with Horner's method.
2047:
2035:
2080:
379:+1 times, one arrives at Estrin's scheme for parallel evaluation of a polynomial:
2094:
2025:"Organization of computer systems—The fixed plus variable structure computer"
2020:
28:
2039:
247:, may be computed in parallel. They may also be evaluated using a native
36:
153:, one can group adjacent terms into sub-expressions of the form (
254:
This grouping can then be repeated to get a polynomial in
2057:
Elementary
Functions: Algorithms and Implementation
2092:
604:) to mean the nth order polynomial of the form:
467: ≤ 1, the computation is complete and
93:/2⌉ independent operations (plus one to compute
53:
2083:, a Sage library using an improved scheme (
1239:In full detail, consider the evaluation of
16:Polynomial Evaluation Algorithm by Estrin
2059:(2nd ed.). Birkhäuser. p. 58.
2093:
2054:
2019:
662:Written with Estrin's scheme we have:
485:(in parallel with the computation of
161:) and rewrite it as a polynomial in
243:Each of these sub-expressions, and
13:
2074:
14:
2112:
2032:Proc. Western Joint Comput. Conf
100:Given an arbitrary polynomial
1:
2013:
2055:Muller, Jean-Michel (2005).
54:Description of the algorithm
7:
588:
10:
2117:
553:This performs a total of
58:Estrin's scheme operates
41:evaluation of polynomials
2034:. San Francisco: 33–40.
2040:10.1145/1460361.1460365
549:using Estrin's scheme.
414:for all 0 ≤
62:, converting a degree-
585:+1 operations long.
474:is the final answer.
477:Otherwise, compute
443: = 0 and
249:multiply–accumulate
2101:Numerical analysis
21:numerical analysis
2085:extended abstract
31:), also known as
2108:
2070:
2051:
2029:
584:
574:
570:
560:
544:
537:
428:
421:
378:
368:
84:
77:
74:≥2) to a degree-
2116:
2115:
2111:
2110:
2109:
2107:
2106:
2105:
2091:
2090:
2081:fast_polynomial
2077:
2075:Further reading
2067:
2027:
2016:
1994:
1987:
1977:
1970:
1956:
1949:
1939:
1932:
1914:
1907:
1897:
1890:
1876:
1869:
1859:
1852:
1829:
1822:
1812:
1805:
1791:
1784:
1774:
1767:
1749:
1742:
1732:
1725:
1711:
1704:
1694:
1687:
1665:
1658:
1648:
1641:
1627:
1620:
1610:
1603:
1589:
1582:
1572:
1565:
1551:
1544:
1534:
1527:
1509:
1502:
1492:
1485:
1475:
1468:
1458:
1451:
1441:
1434:
1424:
1417:
1407:
1400:
1390:
1383:
1368:
1361:
1355:
1348:
1341:
1334:
1328:
1321:
1314:
1307:
1301:
1294:
1287:
1280:
1273:
1266:
1245:
1225:
1218:
1200:
1193:
1183:
1176:
1162:
1155:
1145:
1138:
1127:
1116:
1098:
1091:
1081:
1074:
1060:
1053:
1043:
1036:
1025:
1006:
999:
989:
982:
968:
961:
951:
944:
933:
918:
908:
901:
887:
880:
870:
863:
852:
837:
830:
816:
809:
799:
792:
781:
770:
756:
749:
739:
732:
721:
706:
699:
689:
682:
671:
657:
648:
638:
628:
621:
609:
598:
591:
582:
578:
572:
568:
564:
558:
545:
542:
535:
526:
516:
509:
490:
473:
458:
452:
442:
426:
419:
410:
399:
388:
376:
372:
366:
365:Repeating this
342:
335:
325:
318:
304:
297:
287:
280:
224:
217:
203:
196:
186:
179:
150:
141:
131:
121:
114:
82:
75:
56:
47:Horner's method
33:Estrin's method
25:Estrin's scheme
17:
12:
11:
5:
2114:
2104:
2103:
2089:
2088:
2076:
2073:
2072:
2071:
2065:
2052:
2021:Estrin, Gerald
2015:
2012:
2011:
2010:
1992:
1985:
1975:
1968:
1954:
1947:
1937:
1930:
1912:
1905:
1895:
1888:
1874:
1867:
1857:
1850:
1841:
1827:
1820:
1810:
1803:
1789:
1782:
1772:
1765:
1747:
1740:
1730:
1723:
1709:
1702:
1692:
1685:
1673:
1663:
1656:
1646:
1639:
1625:
1618:
1608:
1601:
1587:
1580:
1570:
1563:
1549:
1542:
1532:
1525:
1513:
1507:
1500:
1490:
1483:
1473:
1466:
1456:
1449:
1439:
1432:
1422:
1415:
1405:
1398:
1388:
1381:
1369:
1366:
1359:
1353:
1346:
1339:
1332:
1326:
1319:
1312:
1305:
1299:
1292:
1285:
1278:
1271:
1264:
1243:
1237:
1236:
1233:
1223:
1216:
1198:
1191:
1181:
1174:
1160:
1153:
1143:
1136:
1125:
1120:
1114:
1096:
1089:
1079:
1072:
1058:
1051:
1041:
1034:
1023:
1018:
1004:
997:
987:
980:
966:
959:
949:
942:
931:
926:
916:
906:
899:
885:
878:
868:
861:
850:
845:
835:
828:
814:
807:
797:
790:
779:
774:
768:
754:
747:
737:
730:
719:
714:
704:
697:
687:
680:
669:
655:
646:
636:
626:
619:
607:
596:
590:
587:
576:
562:
551:
550:
534:
524:
514:
507:
493:
488:
475:
471:
461:
456:
447:
437:
433:is even, then
404:
394:
386:
370:
340:
333:
323:
316:
302:
295:
285:
278:
222:
215:
201:
194:
184:
177:
148:
139:
129:
119:
112:
85:polynomial in
66:polynomial in
55:
52:
39:for numerical
15:
9:
6:
4:
3:
2:
2113:
2102:
2099:
2098:
2096:
2086:
2082:
2079:
2078:
2068:
2066:0-8176-4372-9
2062:
2058:
2053:
2049:
2045:
2041:
2037:
2033:
2026:
2022:
2018:
2017:
2009:
2005:
2001:
1997:
1991:
1984:
1980:
1974:
1967:
1963:
1959:
1953:
1946:
1942:
1936:
1929:
1925:
1921:
1917:
1911:
1904:
1900:
1894:
1887:
1883:
1879:
1873:
1866:
1862:
1856:
1849:
1845:
1842:
1840:
1836:
1832:
1826:
1819:
1815:
1809:
1802:
1798:
1794:
1788:
1781:
1777:
1771:
1764:
1760:
1756:
1752:
1746:
1739:
1735:
1729:
1722:
1718:
1714:
1708:
1701:
1697:
1691:
1684:
1680:
1677:
1674:
1672:
1668:
1662:
1655:
1651:
1645:
1638:
1634:
1630:
1624:
1617:
1613:
1607:
1600:
1596:
1592:
1586:
1579:
1575:
1569:
1562:
1558:
1554:
1548:
1541:
1537:
1531:
1524:
1520:
1517:
1514:
1512:
1506:
1499:
1495:
1489:
1482:
1478:
1472:
1465:
1461:
1455:
1448:
1444:
1438:
1431:
1427:
1421:
1414:
1410:
1404:
1397:
1393:
1387:
1380:
1376:
1373:
1370:
1365:
1358:
1352:
1345:
1338:
1331:
1325:
1318:
1311:
1304:
1298:
1291:
1284:
1277:
1270:
1263:
1259:
1256:
1253:
1252:
1251:
1249:
1242:
1234:
1232:
1228:
1222:
1215:
1211:
1207:
1203:
1197:
1190:
1186:
1180:
1173:
1169:
1165:
1159:
1152:
1148:
1142:
1135:
1131:
1124:
1121:
1119:
1113:
1109:
1105:
1101:
1095:
1088:
1084:
1078:
1071:
1067:
1063:
1057:
1050:
1046:
1040:
1033:
1029:
1022:
1019:
1017:
1013:
1009:
1003:
996:
992:
986:
979:
975:
971:
965:
958:
954:
948:
941:
937:
930:
927:
925:
921:
915:
911:
905:
898:
894:
890:
884:
877:
873:
867:
860:
856:
849:
846:
844:
840:
834:
827:
823:
819:
813:
806:
802:
796:
789:
785:
778:
775:
773:
767:
763:
759:
753:
746:
742:
736:
729:
725:
718:
715:
713:
709:
703:
696:
692:
686:
679:
675:
668:
665:
664:
663:
660:
659:
651:
645:
641:
635:
631:
625:
618:
614:
610:
603:
599:
586:
581:
567:
556:
548:
540:
533:
529:
523:
519:
513:
506:
502:
498:
494:
491:
484:
480:
476:
470:
466:
462:
459:
453: =
450:
446:
440:
436:
432:
424:
418: ≤
417:
413:
408:
403:
398:
393:
389:
382:
381:
380:
375:
363:
361:
357:
353:
349:
345:
339:
332:
328:
322:
315:
311:
307:
301:
294:
290:
284:
277:
273:
269:
265:
261:
257:
252:
250:
246:
241:
239:
235:
231:
227:
221:
214:
210:
206:
200:
193:
189:
183:
176:
172:
168:
164:
160:
157: +
156:
152:
144:
138:
134:
128:
124:
118:
111:
107:
103:
98:
96:
92:
88:
80:
73:
69:
65:
61:
51:
48:
44:
42:
38:
34:
30:
29:Gerald Estrin
26:
22:
2056:
2031:
2023:(May 1960).
2007:
2003:
1999:
1995:
1989:
1982:
1978:
1972:
1965:
1961:
1957:
1951:
1944:
1940:
1934:
1927:
1923:
1919:
1915:
1909:
1902:
1898:
1892:
1885:
1881:
1877:
1871:
1864:
1860:
1854:
1847:
1843:
1838:
1834:
1830:
1824:
1817:
1813:
1807:
1800:
1796:
1792:
1786:
1779:
1775:
1769:
1762:
1758:
1754:
1750:
1744:
1737:
1733:
1727:
1720:
1716:
1712:
1706:
1699:
1695:
1689:
1682:
1678:
1675:
1670:
1666:
1660:
1653:
1649:
1643:
1636:
1632:
1628:
1622:
1615:
1611:
1605:
1598:
1594:
1590:
1584:
1577:
1573:
1567:
1560:
1556:
1552:
1546:
1539:
1535:
1529:
1522:
1518:
1515:
1510:
1504:
1497:
1493:
1487:
1480:
1476:
1470:
1463:
1459:
1453:
1446:
1442:
1436:
1429:
1425:
1419:
1412:
1408:
1402:
1395:
1391:
1385:
1378:
1374:
1371:
1363:
1356:
1350:
1343:
1336:
1329:
1323:
1316:
1309:
1302:
1296:
1289:
1282:
1275:
1268:
1261:
1257:
1254:
1247:
1240:
1238:
1230:
1226:
1220:
1213:
1209:
1205:
1201:
1195:
1188:
1184:
1178:
1171:
1167:
1163:
1157:
1150:
1146:
1140:
1133:
1129:
1122:
1117:
1111:
1107:
1103:
1099:
1093:
1086:
1082:
1076:
1069:
1065:
1061:
1055:
1048:
1044:
1038:
1031:
1027:
1020:
1015:
1011:
1007:
1001:
994:
990:
984:
977:
973:
969:
963:
956:
952:
946:
939:
935:
928:
923:
919:
913:
909:
903:
896:
892:
888:
882:
875:
871:
865:
858:
854:
847:
842:
838:
832:
825:
821:
817:
811:
804:
800:
794:
787:
783:
776:
771:
765:
761:
757:
751:
744:
740:
734:
727:
723:
716:
711:
707:
701:
694:
690:
684:
677:
673:
666:
661:
653:
649:
643:
639:
633:
629:
623:
616:
612:
605:
601:
594:
592:
579:
565:
554:
552:
546:
538:
531:
527:
521:
517:
511:
504:
500:
496:
486:
482:
478:
468:
464:
454:
448:
444:
438:
434:
430:
422:
415:
411:
406:
401:
396:
391:
384:
373:
364:
359:
355:
351:
347:
343:
337:
330:
326:
320:
313:
309:
305:
299:
292:
288:
282:
275:
271:
267:
263:
259:
255:
253:
244:
242:
237:
233:
229:
225:
219:
212:
208:
204:
198:
191:
187:
181:
174:
170:
166:
162:
158:
154:
146:
142:
136:
132:
126:
122:
116:
109:
105:
101:
99:
94:
90:
86:
78:
71:
67:
63:
57:
45:
32:
24:
18:
60:recursively
2014:References
615:) =
495:Evaluate
37:algorithm
2095:Category
2048:16384320
589:Examples
383:Compute
35:, is an
1926:) + (((
1844:Step 4:
1676:Step 3:
1516:Step 2:
1372:Step 1:
1255:Inputs:
429:. (If
89:using ⌈
27:(after
2063:
2046:
1964:) + ((
1884:) + ((
1799:) + ((
1719:) + ((
652:+ ⋯ +
530:+ ⋯ +
354:+ ⋯ =
329:) + (
312:) + ((
274:) = ((
232:+ ⋯ =
145:+ ⋯ +
2044:S2CID
2028:(PDF)
1981:) + (
1943:) + (
1901:) + (
1863:) + (
1816:) + (
1778:) + (
1736:) + (
1698:) + (
1652:) + (
1614:) + (
1576:) + (
1538:) + (
1187:) + (
1149:) + (
1132:) = (
1085:) + (
1047:) + (
1030:) = (
993:) + (
955:) + (
938:) = (
874:) + (
857:) = (
803:) + (
786:) = (
743:) + (
726:) = (
693:) + (
676:) = (
593:Take
291:) + (
190:) + (
173:) = (
70:(for
2061:ISBN
1761:, ((
1681:, ((
1170:+ ((
1068:+ ((
976:+ ((
912:) +
895:+ ((
503:) =
266:) =
108:) =
2036:doi
1846:(((
1635:, (
1597:, (
1559:, (
1521:, (
1250:):
1212:+ (
824:+ (
575:log
561:log
463:If
369:log
362:).
240:).
211:+ (
97:).
19:In
2097::
2087:).
2042:.
2030:.
1993:15
1986:14
1976:13
1969:12
1955:11
1948:10
1828:15
1821:14
1811:13
1804:12
1790:11
1783:10
1664:15
1657:14
1647:13
1640:12
1626:11
1619:10
1508:15
1501:14
1496:,
1491:13
1484:12
1479:,
1474:11
1467:10
1462:,
1445:,
1428:,
1411:,
1394:,
1377:,
1367:15
1362:,
1360:14
1354:13
1349:,
1347:12
1342:,
1340:11
1335:,
1333:10
1322:,
1315:,
1308:,
1295:,
1288:,
1281:,
1274:,
1267:,
1260:,
1244:15
1229:)
1219:+
1204:)
1194:+
1177:+
1166:)
1156:+
1139:+
1110:+
1102:)
1092:+
1075:+
1064:)
1054:+
1037:+
1010:)
1000:+
983:+
972:)
962:+
945:+
902:+
891:)
881:+
864:+
841:)
831:+
820:)
810:+
793:+
764:+
760:)
750:+
733:+
710:)
700:+
683:+
642:+
632:+
622:+
541:/2
520:+
510:+
492:).
481:=
460:.)
451:/2
441:+1
425:/2
409:+1
400:+
390:=
336:+
319:+
298:+
281:+
258::
218:+
197:+
180:+
165::
159:Bx
135:+
125:+
115:+
81:/2
43:.
23:,
2069:.
2050:.
2038::
2008:x
2006:)
2004:x
2002:)
2000:x
1998:)
1996:x
1990:C
1988:+
1983:C
1979:x
1973:C
1971:+
1966:C
1962:x
1960:)
1958:x
1952:C
1950:+
1945:C
1941:x
1938:9
1935:C
1933:+
1931:8
1928:C
1924:x
1922:)
1920:x
1918:)
1916:x
1913:7
1910:C
1908:+
1906:6
1903:C
1899:x
1896:5
1893:C
1891:+
1889:4
1886:C
1882:x
1880:)
1878:x
1875:3
1872:C
1870:+
1868:2
1865:C
1861:x
1858:1
1855:C
1853:+
1851:0
1848:C
1839:x
1837:)
1835:x
1833:)
1831:x
1825:C
1823:+
1818:C
1814:x
1808:C
1806:+
1801:C
1797:x
1795:)
1793:x
1787:C
1785:+
1780:C
1776:x
1773:9
1770:C
1768:+
1766:8
1763:C
1759:x
1757:)
1755:x
1753:)
1751:x
1748:7
1745:C
1743:+
1741:6
1738:C
1734:x
1731:5
1728:C
1726:+
1724:4
1721:C
1717:x
1715:)
1713:x
1710:3
1707:C
1705:+
1703:2
1700:C
1696:x
1693:1
1690:C
1688:+
1686:0
1683:C
1679:x
1671:x
1669:)
1667:x
1661:C
1659:+
1654:C
1650:x
1644:C
1642:+
1637:C
1633:x
1631:)
1629:x
1623:C
1621:+
1616:C
1612:x
1609:9
1606:C
1604:+
1602:8
1599:C
1595:x
1593:)
1591:x
1588:7
1585:C
1583:+
1581:6
1578:C
1574:x
1571:5
1568:C
1566:+
1564:4
1561:C
1557:x
1555:)
1553:x
1550:3
1547:C
1545:+
1543:2
1540:C
1536:x
1533:1
1530:C
1528:+
1526:0
1523:C
1519:x
1511:x
1505:C
1503:+
1498:C
1494:x
1488:C
1486:+
1481:C
1477:x
1471:C
1469:+
1464:C
1460:x
1457:9
1454:C
1452:+
1450:8
1447:C
1443:x
1440:7
1437:C
1435:+
1433:6
1430:C
1426:x
1423:5
1420:C
1418:+
1416:4
1413:C
1409:x
1406:3
1403:C
1401:+
1399:2
1396:C
1392:x
1389:1
1386:C
1384:+
1382:0
1379:C
1375:x
1364:C
1357:C
1351:C
1344:C
1337:C
1330:C
1327:9
1324:C
1320:8
1317:C
1313:7
1310:C
1306:6
1303:C
1300:5
1297:C
1293:4
1290:C
1286:3
1283:C
1279:2
1276:C
1272:1
1269:C
1265:0
1262:C
1258:x
1248:x
1246:(
1241:P
1235:…
1231:x
1227:x
1224:9
1221:C
1217:8
1214:C
1210:x
1208:)
1206:x
1202:x
1199:7
1196:C
1192:6
1189:C
1185:x
1182:5
1179:C
1175:4
1172:C
1168:x
1164:x
1161:3
1158:C
1154:2
1151:C
1147:x
1144:1
1141:C
1137:0
1134:C
1130:x
1128:(
1126:9
1123:P
1118:x
1115:8
1112:C
1108:x
1106:)
1104:x
1100:x
1097:7
1094:C
1090:6
1087:C
1083:x
1080:5
1077:C
1073:4
1070:C
1066:x
1062:x
1059:3
1056:C
1052:2
1049:C
1045:x
1042:1
1039:C
1035:0
1032:C
1028:x
1026:(
1024:8
1021:P
1016:x
1014:)
1012:x
1008:x
1005:7
1002:C
998:6
995:C
991:x
988:5
985:C
981:4
978:C
974:x
970:x
967:3
964:C
960:2
957:C
953:x
950:1
947:C
943:0
940:C
936:x
934:(
932:7
929:P
924:x
922:)
920:x
917:6
914:C
910:x
907:5
904:C
900:4
897:C
893:x
889:x
886:3
883:C
879:2
876:C
872:x
869:1
866:C
862:0
859:C
855:x
853:(
851:6
848:P
843:x
839:x
836:5
833:C
829:4
826:C
822:x
818:x
815:3
812:C
808:2
805:C
801:x
798:1
795:C
791:0
788:C
784:x
782:(
780:5
777:P
772:x
769:4
766:C
762:x
758:x
755:3
752:C
748:2
745:C
741:x
738:1
735:C
731:0
728:C
724:x
722:(
720:4
717:P
712:x
708:x
705:3
702:C
698:2
695:C
691:x
688:1
685:C
681:0
678:C
674:x
672:(
670:3
667:P
658:x
656:n
654:C
650:x
647:3
644:C
640:x
637:2
634:C
630:x
627:1
624:C
620:0
617:C
613:x
611:(
608:n
606:P
602:x
600:(
597:n
595:P
583:⌋
580:n
577:2
573:⌊
569:⌋
566:n
563:2
559:⌊
555:n
547:y
543:⌋
539:n
536:⌊
532:D
528:y
525:2
522:D
518:y
515:1
512:D
508:0
505:D
501:y
499:(
497:Q
489:i
487:D
483:x
479:y
472:0
469:D
465:n
457:n
455:C
449:n
445:D
439:n
435:C
431:n
427:⌋
423:n
420:⌊
416:i
412:x
407:i
405:2
402:C
397:i
395:2
392:C
387:i
385:D
377:⌋
374:n
371:2
367:⌊
360:x
358:(
356:R
352:x
350:)
348:x
346:)
344:x
341:7
338:C
334:6
331:C
327:x
324:5
321:C
317:4
314:C
310:x
308:)
306:x
303:3
300:C
296:2
293:C
289:x
286:1
283:C
279:0
276:C
272:x
270:(
268:Q
264:x
262:(
260:P
256:x
245:x
238:x
236:(
234:Q
230:x
228:)
226:x
223:5
220:C
216:4
213:C
209:x
207:)
205:x
202:3
199:C
195:2
192:C
188:x
185:1
182:C
178:0
175:C
171:x
169:(
167:P
163:x
155:A
151:x
149:n
147:C
143:x
140:3
137:C
133:x
130:2
127:C
123:x
120:1
117:C
113:0
110:C
106:x
104:(
102:P
95:x
91:n
87:x
83:⌋
79:n
76:⌊
72:n
68:x
64:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.