How to do big integer inversion/division with middle product, power series?

[R. Gerbicz]

See http://cr.yp.to/bib/2004/hanrot-middle.pdf . I've working algorithms for power series, but don't know how to use these for bigintegers.
See for example the inversion algorithm at page 421.

My method for big integers is that: use a base say B=10^5 (or B=2^17 if you want power of two), work in big endians, and
assume that a_0=1, so the input's most significant limb is one, with this the advantage is that all numbers in the MP-inv algorithm will be integers
(obviously as we use only one division: 1/a_0). The problem is with carries, first assume that we "normalize" the number only at line 5, so at

5. Return [α0,...,αn−p−1,−γ0,...,−γp−1].

but even with this we get wrong answer. Example from my Pari code:
For a=[1,2,5,4] the power serie inversion is

? mpinv(a)
%12 = [1, -2.0000000000000000000000000000000000000, -1.0000000000000000000000000000000000000 + 0.E-37*I, 8.0000000000000000000000000000000000000 + 0.E-37*I]

so with usual rounding this is [1,-2,-1,8] (note that the answer is purely real). What is good, as:

? 1/(1+2*x+5*x^2+4*x^3)+O(x^4)
%15 = 1 - 2*x - x^2 + 8*x^3 + O(x^4)

and with normalization I get for a=[1,2,5,4] is

? mpinv2(a,B)
%17 = [0, 99996, 7, 99992]

which is clearly wrong:

a=[1,2,5,4];
v=[0, 99996, 7, 99992];
B=10^5;
? r1=sum(i=1,4,a[i]*B^(1-i))
%19 = 250005000125001/250000000000000
? r2=sum(i=1,4,v[i]*B^(1-i))
%20 = 124995000099999/125000000000000
? 
? r1*r2*1.0
%21 = 0.99998000049999200007999919996800000000

Note that we need to use normalization steps as even for normalized input the output without any normalization blows up, the coefficients will be huge integers,
example for this:

? a=vector(20,i,random(B));a[1]=1;
? mpinv(a)
%34 = [1, -17014.000000000000000000000000000000000, 289413878.00000000000000000000000000000 + 0.E-30*I, -4923027481444.0000000000000000000000001 - 5.169878828456422968 E-26*I, 83742354548988810.000000000000000000002 + 8.798444448855704369 E-22*I, -1424485638530618079506.0000000000000003 - 1.5265566588595902431 E-16*I, 24230980192859705490966612.000000000004 + 2.5972501926929680850 E-12*I, -412177129221467611304936504259.00000007 - 4.284027171896909181 E-8*I, 7011271706759636339700291066529881.0014 + 0.0008239671582275176488*I, -1.1926409172400987459638461511224837256 E38 - 13.499633779419586877*I, 2.0287223444841847134203395932624665955 E42 - 212992.00000000000000*I, -3.4509249947030320326240355024345413364 E46 + 3623662387.200000000*I, 5.8701395740253599804770552781352905848 E50 - 61639717937152.00001*I, -9.9853050041454031824586814693595971199 E54 + 943629863050928141.3*I, 1.6985339917128941911957849914191702055 E59 - 1.6050972144248543722 E22*I, -2.8892634925086633861384262341403653756 E63 - 6.300746569284726370 E24*I, 4.9147344532828213055274267761806581323 E67 + 1.0722148108184756819 E29*I, -8.3601287348536161294119718123287343400 E71 + 8.942693800970157870 E32*I, 1.4220860379677396564528247833726123799 E76 + 1.7801307452648963917 E38*I, -2.4190162179580288142799623261481058078 E80 - 1.9798745653388746952 E42*I]

[jasonp]

Maybe ask Paul Zimmermann?