mulmod für 64 bit

volkard

suche mulmod für 64-bittige argumente.

für 32 bit hab ich was:

u32 mulMod(u32 a,u32 b,u32 m){
	return u64(a)*u64(b)%u64(m);
}

oder mit ms-asm

#pragma warning(disable:4035)//warning C4035: no return value
inline u32 mulMod(u32 a,u32 b,u32 m)
{
	_asm    mov     eax,dword ptr a //eax=a
		_asm    mov     esi,dword ptr b //esi=b
		_asm    mov             edi,dword ptr m //edi=m
		_asm    mul             esi                             //edx:eax=esi*eax
		_asm    div             edi                             //eax R edx=edx:eax/edi
		_asm    mov             eax,edx                 //eax=edx
}
#pragma warning(default:4035)

für 64 bit müßte das zwischenergebnis aber 128 bit lang sein und ich bin zu doof, das einigermaßen performant selber zu schaffen. kennt jemand nen link oder hat code? egal, ob asm oder c++.

edit: hab was gefunden.

u32 mulMod(u32 a,u32 b,u32 m){
    // return a*b (mod m).
	// take special care of unsigned quantities and overflow.
	//
    unsigned int z;
    unsigned int y = a;
    int t;
    z = 0;
    for (;;) {
        unsigned int c = b/2;
        if (c*2 != b) {
            z += y;
            if (z < y || z >= m) z -=m;
        }
        b = c;
        if (!b) break;
        t = y;
        y <<= 1;
        if (t < 0 || y >= m) y -= m;
    }
    return z;

der code läßt sich offensichtlich auch mit u64 betreiben.