If I have integer number N that I know factorization of, what is the fastest (most efficient) way of computing 1/N as a floating point number? Big floating (or integer) arithmetics should be used for that.

I want to do this in C++ (or to do experimental runs in Python).

My N is very huge, Giga/Tera-bits in size. Resulting floating point N should also have huge precision, around the same bit-size as initial N.

Precise floating value is needed meaning if I request floating precision Log2(N) bits then at least all 95% leading bits of result should be precise (all same bits as in ideal value).

Of course instead of floating point computation one can compute 4^Ceil(Log2(N)) / N as integer division, if it helps and/or simplifies task. For me these two tasks (integer and float) are essentially same, because integer representation is convertible to floating and vice versa.

One important note is that factorization of N has only small prime factors, all of them are 32-bit in size (maybe 64-bit at most, for sure).

I wonder if having factorization of N and also the fact that factors are small, can it help somehow solving the task?

Of course instead of implementing my own division first I tried to use highly-optimized GMP library for this task, but it (as far as I know) doesn't use the fact that N is factorized already.

Can anyone suggest if I'm about to implement my own function for this, just to figure out experimentally if it will be faster than GMP's, then what kind of algorithm should I use?

I figured out that there are 3 algorithms that can be used here 1) Long Division, which is a school-grade algorithm. 2) Barrett Reduction. 3) Montgomery Reduction.

Actually I don't know any other algorithms. Can you suggest other? Both Barrett and Montgomery reductions can help only if same prime factor repeats many times, otherwise single-time division is not worth precomputation that is needed for Barrett and Montgomery.

Also Barrett/Montgomery reductions still need one-time computing 4^Ceil(Log2(N)) / PrimeDivisor. So they don't save you from doing Long Division algorithm.

Definitely for Long Division algorithm I will be using 2^64 as a base instead of base 10 (as in school).

I already implemented my own experimental library with Long Division and all other integer arithmetics algorithms plus elliptic curve arithmetics too. Right now it is generic and hence not faster than GMP. Now I need special division algo that can be at least several times faster than GMP.

Sure that in Long Division I can use Montgomery and Barrett, because at each step it needs short division (128 bit integer divided by 64 bit integer) if it give any boost.

Also at each step of Long Division I can use Fast Fourier Transform or Number Theoretic Transform for doing multiplication.

Above are the only optimizations that I know about. Are there any other optimizations possible? Maybe FFT can be used for directly doing division (not just for multiplication)?