How would you deal with say a 6x6 limb multiply (where a limb is by the old definition). How would thid maintain performance for such sizes?
Bill. On 24 June 2010 07:10, Sergey Bochkanov <sergey.bochka...@alglib.net> wrote: > Hello, Bill. > > You wrote 22 июня 2010 г., 3:30:30: >> BSDNT >> ...... >> scratch. One idea I had was to write all the low level routines in >> LLVM instead of assembly, then just build suitable optimisations into >> LLVM so that nice assembly is automatically produced. This is entirely >> feasible and would mean only one lot of low level routines would ever >> need to be written, rather than a different set for each platform >> ..... >> However, LLVM doesn't support carry propagation well > > Automatic translation like that (ALGLIB project) saves me a lot of > time. Implementing things twice is twice as hard as implementing them > once. But implementing then 10 times would be 10^2 times harder. So > using LLBM is a great idea, but lack of carry propagation is a serious > drawback. I think it is possible to extend LLVM with carry support, > but it will require too much time. > > > What do you think about another idea (which came from numerical linear > algebra)? It is called 'blocking'. > > In principle all your library could be written entirely in C, but it > can't because C doesn't supports operations with limbs with carry > propagation. The only thing you need to have efficient library is to > have efficient add/sub/mul/div for limbs (single limbs, not sequences > of limbs), right? > > Imagine library with limbs which are 1024 bytes long. You just have to > code in assembler only four operations: add two limbs (with optional > carry), sub two limbs, mul two limbs, div two limbds. Implement them > as separate functions. > > Then you can write "generic C" library which calls these functions > instead of using arithmetic operators provides by language like + or > *. You have to write only four functions, and now you have efficient > mpn_add_n, mpn_add_1, mpn_add, mpn_sub_n, etc. And these mpn > functions will be written entirely in C. > > Of course, you will have function call penalty, but it should become > less significant with such large limbs. As in numerical linear > algebra. > > What do you think about it? > > -- > With best regards, > Sergey mailto:sergey.bochka...@alglib.net > > -- > You received this message because you are subscribed to the Google Groups > "mpir-devel" group. > To post to this group, send email to mpir-de...@googlegroups.com. > To unsubscribe from this group, send email to > mpir-devel+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/mpir-devel?hl=en. > > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-de...@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.