28{
33 typedef typename compositor_t::function function_t;
34
35
36 T composites[] =
37 {
38 199203677, 779234623, 843093203, 883543291, 1197162971,
39 1282615157, 1552390397, 1765737859, 1878769589, 1993904873,
40 2257133471, 2520523529, 2579094799, 2853450949, 2935025369,
41 3095780533, 3164132249, 3408963511, 4260042859, 4608613981,
42 4654875857, 5085931997, 7278175081, 7289187463, 9206112101
43 };
44
46
47 symbol_table_t symbol_table;
48
49 symbol_table.add_vector ("composites", composites);
50 symbol_table.add_function("println" , println );
51
52 compositor_t compositor(symbol_table);
53
54 compositor.add(function_t()
55 .name("gcd")
56 .var("x") .var("y")
57 .expression
58 (
59 " x := abs(x); "
60 " y := abs(y); "
61 " while (0 != y) "
62 " { "
63 " var r := x % y; "
64 " x := y; "
65 " y := r; "
66 " }; "
67 " x "
68 ));
69
70 compositor.add(function_t()
71 .name("pollard_rho")
72 .var("n")
73 .expression
74 (
75 " var c := 10; "
76 " var a1 := 1 + c; "
77 " var a2 := 11 + c; "
78 " "
79 " while (gcd(n, a2 - a1) == 1) "
80 " { "
81 " /* The Tortoise */ "
82 " a1 := (a1^2 + c) % n; "
83 " "
84 " /* The Hare */ "
85 " a2 := (a2^2 + c) % n; "
86 " a2 := (a2^2 + c) % n; "
87 " }; "
88 " "
89 " var g := gcd(n, a2 - a1); "
90 " "
91 " n / g "
92 ));
93
94 const std::string factorize_composites_program =
95 " for (var i := 0; i < composites[]; i += 1) "
96 " { "
97 " var n := composites[i]; "
98 " var factor0 := pollard_rho(n); "
99 " var factor1 := n / factor0; "
100 " "
101 " if ((factor0 * factor1 == n) and (factor0 != 1)) "
102 " { "
103 " println('n: ', n, ' factors: { ', factor0 ,' , ', factor1 ,' } '); "
104 " } "
105 " else "
106 " { "
107 " println('failed to factorize ', n); "
108 " } "
109 " } "
110 " ";
111 expression_t expression;
112 expression.register_symbol_table(symbol_table);
113
114 parser_t parser;
115 parser.compile(factorize_composites_program,expression);
116
117 expression.value();
118}
