All geek questions in one place

Lehmer Extends GCD Algorithm Implementation

Performing my own implementation of BigInteger, I was stuck with the advanced GCD algorithm, which is fundamental to finding the modular multiplicative inverse. Since the well-known Euclidean approach is too slow, and hybrid and binary algorithms are only 5-10 times faster, the choice was to modify the Lehmer classical algorithm. But the difficulty is that when it comes to Lehmer's description, all the books I found (Knuth, Handbook of Applied Cryptography, Internets, etc.) have the same disadvantages:

  • The explanation is based on several tricks:
    • input numbers always have the same length;
    • An abstract processor has signed registers, which can contain either a digit or a sign;
    • an abstract processor has semi-unlimited registers, i.e. e. It is never crowded.
  • Only the basic GCD algorithm is provided without focusing on inverse cofactors.

Regarding the first problem, I was initially surprised that I could not find a realistic implementation (do not point me to the GNU MP library - this is not a source for study), but finally inspired the decompilation of the Microsoft implementation from .Net 4.0, which, obviously, based on ideas from the article "The Lechmer-Euclidean Two-Digit Algorithm for Finding GCD Long Integers " by Jebelian. The resulting function is great, it looks scary, but it works just fine.

But the Microsoft library provides only basic functions, no cofactors are calculated. Well, to be precise, some cofactors are computed during the stenographic step, and in the first stage, these cofactors are simply the original ones, but after the long step is performed, they no longer correspond. My current solution is to update the “real” cofactors in parallel with the “substitute” ones (with the exception of the very first step), but this reduces productivity to zero: now the function ends only 25-50% faster than the binary method in the main mode. Thus, the problem is that , while the input numbers are completely updated only when the steps are taken step by step, cofactors are also updated at each iteration of the shortened step , thereby destroying almost any benefit from Lemmer's approach.

To speed things up a bit, I implemented the "fused multiply-add" function, because "smooth multiple-subtraction-subtract" really helps to update input numbers, but this time the effect was negligible. Another improvement is based on the fact that usually only one cofactor is needed, so the other can simply not be calculated. This should halve overhead costs (and even more so since the second number is usually much less than the first), however, in practice, overhead costs are reduced only by 25-50% of the expected.

Therefore, my questions boil down to the following:

  • Is there a full-scale explanation of the Lehmer algorithm related to practical implementation on real equipment (with unsigned words of a limited size)?
  • Same as above, but with respect to advanced GCD calculation.

So, as far as I am satisfied with the implementation of the basic algorithm, the opposite applies to the extended mode of operation, which is the main one in my case.

+6
source share
1 answer

Finally, I consulted with a mathematician, and he quickly understood the correct formulas - very similar to the ones I tried, a little differently. This allowed updating the cofactors only at stages with a long step, at the same time that the numbers entered were completely updated.

However, to my great surprise, this measure alone had a slight effect on performance. Only when I re-implemented it as "fused (A × X + B × Y)" did the speed improvement become noticeable. When calculating both cofactors, it now works at 56% for 5-digit numbers and 34% for 32 thousand. Digits compared to the pure Lehmer GCD algorithm; for one cofactor, the rate is 70% and 52%, respectively. With previous implementations, it was only from 33% to 7% for both cofactors and from 47% to 14% for one cofactor, so my dissatisfaction was obvious.

As for writing paper like andy256 , recommended so that other developers do not have the same problem, it will not be easy. I already wrote a “small” paper when I explained my current implementation of mathematics, and it pretty quickly exceeded three sheets of A4 format - although it contained the main ideas, without detailed explanations, checking for overflow, branching, turning, etc. Now I partially understand why Knut and the others used dirty tricks to keep the story shorter. Currently, I have no idea how to achieve the same level of simplicity without losing thoroughness; you may need several large flowcharts in conjunction with comments.

Update . It seems that I will not be able to complete and publish the library in the near future (still no luck in understanding the Newton-Raphson division and the abbreviation Montgomery), so I will simply publish the resulting function for those who are interested.

The code does not include obvious functions like ComputeGCD_Euclid and generic routines like ComputeDivisionLonghand . There are also no comments in the code (with some exceptions) - you should be familiar with the idea of ​​Lemmer as a whole and the two-digit abbreviated technique mentioned above if you want to understand it and integrate it into your own library.

Overview of the representation of numbers in my library. The numbers are unsigned 32-bit integers, so you can use 64-bit unambiguous and signed arithmetic if necessary. The numbers are stored in a simple array ( ValueDigits ) from smallest to most significant (LSB), the actual size is stored explicitly ( ValueLength ), i. E. Functions try to predict the size of the result, but do not optimize memory consumption after calculation. Objects have a value type ( struct in .Net), but they reference arrays of numbers; therefore, the objects are invariant, i.e. e. a = a + 1 creates a new object instead of modifying an existing one.

 Public Shared Function ComputeGCD(ByVal uLeft As BigUInteger, ByVal uRight As BigUInteger, ByRef uLeftInverse As BigUInteger, ByRef uRightInverse As BigUInteger, ByVal fComputeLeftInverse As Boolean, ByVal fComputeRightInverse As Boolean) As BigUInteger Dim fSwap As Boolean = False Select Case uLeft.CompareTo(uRight) Case 0 uLeftInverse = Instance.Zero : uRightInverse = Instance.One : Return uRight Case Is < 0 fSwap = fComputeLeftInverse : fComputeLeftInverse = fComputeRightInverse : fComputeRightInverse = fSwap fSwap = True : Swap(uLeft, uRight) End Select Dim uResult As BigUInteger If (uLeft.ValueLength = 1) AndAlso (uRight.ValueLength = 1) Then Dim wLeftInverse As UInt32, wRightInverse As UInt32 uResult = ComputeGCD_Euclid(uLeft.DigitLowest, uRight.DigitLowest, wLeftInverse, wRightInverse) uLeftInverse = wLeftInverse : uRightInverse = wRightInverse ElseIf uLeft.ValueLength <= 2 Then uResult = ComputeGCD_Euclid(uLeft, uRight, uLeftInverse, uRightInverse) Else uResult = ComputeGCD_Lehmer(uLeft, uRight, uLeftInverse, uRightInverse, fComputeLeftInverse, fComputeRightInverse) End If If fSwap Then Swap(uLeftInverse, uRightInverse) Return uResult End Function Private Shared Function ComputeGCD_Lehmer(ByVal uLeft As BigUInteger, ByVal uRight As BigUInteger, ByRef uLeftInverse As BigUInteger, ByRef uRightInverse As BigUInteger, ByVal fComputeLeftInverse As Boolean, ByVal fComputeRightInverse As Boolean) As BigUInteger Dim uLeftCur As BigUInteger = uLeft, uRightCur As BigUInteger = uRight Dim uLeftInvPrev As BigUInteger = Instance.One, uRightInvPrev As BigUInteger = Instance.Zero, uLeftInvCur As BigUInteger = uRightInvPrev, uRightInvCur As BigUInteger = uLeftInvPrev, fInvInit As Boolean = False, fIterationIsEven As Boolean = True Dim dwLeftCur, dwRightCur As UInt64 Dim wLeftInvPrev, wRightInvPrev, wLeftInvCur, wRightInvCur As UInt32 Dim dwNumeratorMore, dwNumeratorLess, dwDenominatorMore, dwDenominatorLess, dwQuotientMore, dwQuotientLess As UInt64, wQuotient As UInt32 Const nSubtractionThresholdBits As Byte = (5 - 1) Dim ndxDigitMax As Integer, fRightIsShorter As Boolean Dim fResultFound As Boolean = False Dim uRemainder As BigUInteger = uRightCur, uQuotient As BigUInteger Dim uTemp As BigUInteger = Nothing, dwTemp, dwTemp2 As UInt64 Do While uLeftCur.ValueLength > 2 ndxDigitMax = uLeftCur.ValueLength - 1 : fRightIsShorter = (uRightCur.ValueLength < uLeftCur.ValueLength) Dim fShorthandStep As Boolean = True, fShorthandIterationIsEven As Boolean If fRightIsShorter AndAlso (uLeftCur.ValueLength - uRightCur.ValueLength > 1) Then fShorthandStep = False If fShorthandStep Then dwLeftCur = uLeftCur.ValueDigits(ndxDigitMax - 1) Or (CULng(uLeftCur.ValueDigits(ndxDigitMax)) << DigitSize.Bits) dwRightCur = uRightCur.ValueDigits(ndxDigitMax - 1) Or If(fRightIsShorter, DigitValue.Zero, CULng(uRightCur.ValueDigits(ndxDigitMax)) << DigitSize.Bits) If ndxDigitMax >= 2 Then Dim nNormHead As Byte = GetNormalizationHead(uLeftCur.ValueDigits(ndxDigitMax)) If nNormHead <> ByteValue.Zero Then dwLeftCur = (dwLeftCur << nNormHead) Or (uLeftCur.ValueDigits(ndxDigitMax - 2) >> (DigitSize.Bits - nNormHead)) dwRightCur = (dwRightCur << nNormHead) Or (uRightCur.ValueDigits(ndxDigitMax - 2) >> (DigitSize.Bits - nNormHead)) End If End If If CUInt(dwRightCur >> DigitSize.Bits) = DigitValue.Zero Then fShorthandStep = False End If If fShorthandStep Then ' First iteration, where overflow may occur in general formulae. If dwLeftCur = dwRightCur Then fShorthandStep = False Else If dwLeftCur = DoubleValue.Full Then dwLeftCur >>= 1 : dwRightCur >>= 1 dwDenominatorMore = dwRightCur : dwDenominatorLess = dwRightCur + DigitValue.One dwNumeratorMore = dwLeftCur + DigitValue.One : dwNumeratorLess = dwLeftCur If (dwNumeratorMore >> nSubtractionThresholdBits) <= dwDenominatorMore Then wQuotient = DigitValue.Zero Do wQuotient += DigitValue.One : dwNumeratorMore -= dwDenominatorMore Loop While dwNumeratorMore >= dwDenominatorMore dwQuotientMore = wQuotient Else dwQuotientMore = dwNumeratorMore \ dwDenominatorMore If dwQuotientMore >= DigitValue.BitHi Then fShorthandStep = False wQuotient = CUInt(dwQuotientMore) End If If fShorthandStep Then If (dwNumeratorLess >> nSubtractionThresholdBits) <= dwDenominatorLess Then wQuotient = DigitValue.Zero Do wQuotient += DigitValue.One : dwNumeratorLess -= dwDenominatorLess Loop While dwNumeratorLess >= dwDenominatorLess dwQuotientLess = wQuotient Else dwQuotientLess = dwNumeratorLess \ dwDenominatorLess End If If dwQuotientMore <> dwQuotientLess Then fShorthandStep = False End If End If End If If fShorthandStep Then ' Prepare for the second iteration. wLeftInvPrev = DigitValue.Zero : wLeftInvCur = DigitValue.One wRightInvPrev = DigitValue.One : wRightInvCur = wQuotient dwTemp = dwLeftCur - wQuotient * dwRightCur : dwLeftCur = dwRightCur : dwRightCur = dwTemp fShorthandIterationIsEven = True fIterationIsEven = Not fIterationIsEven ' Other iterations, no overflow possible(?). Do If fShorthandIterationIsEven Then If dwRightCur = wRightInvCur Then Exit Do dwDenominatorMore = dwRightCur - wRightInvCur : dwDenominatorLess = dwRightCur + wLeftInvCur dwNumeratorMore = dwLeftCur + wRightInvPrev : dwNumeratorLess = dwLeftCur - wLeftInvPrev Else If dwRightCur = wLeftInvCur Then Exit Do dwDenominatorMore = dwRightCur - wLeftInvCur : dwDenominatorLess = dwRightCur + wRightInvCur dwNumeratorMore = dwLeftCur + wLeftInvPrev : dwNumeratorLess = dwLeftCur - wRightInvPrev End If If (dwNumeratorMore >> nSubtractionThresholdBits) <= dwDenominatorMore Then wQuotient = DigitValue.Zero Do wQuotient += DigitValue.One : dwNumeratorMore -= dwDenominatorMore Loop While dwNumeratorMore >= dwDenominatorMore dwQuotientMore = wQuotient Else dwQuotientMore = dwNumeratorMore \ dwDenominatorMore If dwQuotientMore >= DigitValue.BitHi Then Exit Do wQuotient = CUInt(dwQuotientMore) End If If (dwNumeratorLess >> nSubtractionThresholdBits) <= dwDenominatorLess Then wQuotient = DigitValue.Zero Do wQuotient += DigitValue.One : dwNumeratorLess -= dwDenominatorLess Loop While dwNumeratorLess >= dwDenominatorLess dwQuotientLess = wQuotient Else dwQuotientLess = dwNumeratorLess \ dwDenominatorLess End If If dwQuotientMore <> dwQuotientLess Then Exit Do dwTemp = wLeftInvPrev + wQuotient * wLeftInvCur : dwTemp2 = wRightInvPrev + wQuotient * wRightInvCur If (dwTemp >= DigitValue.BitHi) OrElse (dwTemp2 >= DigitValue.BitHi) Then Exit Do wLeftInvPrev = wLeftInvCur : wLeftInvCur = CUInt(dwTemp) wRightInvPrev = wRightInvCur : wRightInvCur = CUInt(dwTemp2) dwTemp = dwLeftCur - wQuotient * dwRightCur : dwLeftCur = dwRightCur : dwRightCur = dwTemp fShorthandIterationIsEven = Not fShorthandIterationIsEven fIterationIsEven = Not fIterationIsEven Loop End If If (Not fShorthandStep) OrElse (wRightInvPrev = DigitValue.Zero) Then ' Longhand step. uQuotient = ComputeDivisionLonghand(uLeftCur, uRightCur, uTemp) : If uTemp.IsZero Then fResultFound = True : Exit Do uRemainder = uTemp fIterationIsEven = Not fIterationIsEven If fComputeLeftInverse Then uTemp = uLeftInvPrev + uQuotient * uLeftInvCur : uLeftInvPrev = uLeftInvCur : uLeftInvCur = uTemp End If If fComputeRightInverse Then uTemp = uRightInvPrev + uQuotient * uRightInvCur : uRightInvPrev = uRightInvCur : uRightInvCur = uTemp End If fInvInit = True uLeftCur = uRightCur : uRightCur = uRemainder Else ' Shorthand step finalization. If Not fInvInit Then If fComputeLeftInverse Then uLeftInvPrev = wLeftInvPrev : uLeftInvCur = wLeftInvCur If fComputeRightInverse Then uRightInvPrev = wRightInvPrev : uRightInvCur = wRightInvCur fInvInit = True Else If fComputeLeftInverse Then ComputeFusedMulMulAdd(uLeftInvPrev, uLeftInvCur, wLeftInvPrev, wLeftInvCur, wRightInvPrev, wRightInvCur) If fComputeRightInverse Then ComputeFusedMulMulAdd(uRightInvPrev, uRightInvCur, wLeftInvPrev, wLeftInvCur, wRightInvPrev, wRightInvCur) End If ComputeFusedMulMulSub(uLeftCur, uRightCur, wLeftInvPrev, wLeftInvCur, wRightInvPrev, wRightInvCur, fShorthandIterationIsEven) End If Loop ' Final rounds: numbers are quite short now. If Not fResultFound Then ndxDigitMax = uLeftCur.ValueLength - 1 : fRightIsShorter = (uRightCur.ValueLength < uLeftCur.ValueLength) If ndxDigitMax = 0 Then dwLeftCur = uLeftCur.ValueDigits(0) dwRightCur = uRightCur.ValueDigits(0) Else dwLeftCur = uLeftCur.ValueDigits(0) Or (CULng(uLeftCur.ValueDigits(1)) << DigitSize.Bits) dwRightCur = uRightCur.ValueDigits(0) Or If(fRightIsShorter, DigitValue.Zero, CULng(uRightCur.ValueDigits(1)) << DigitSize.Bits) End If Do While dwLeftCur >= DigitValue.BitHi Dim dwRemainder As UInt64 = dwLeftCur If (dwRemainder >> nSubtractionThresholdBits) <= dwRightCur Then wQuotient = DigitValue.Zero Do wQuotient += DigitValue.One : dwRemainder -= dwRightCur Loop While dwRemainder >= dwRightCur dwQuotientMore = wQuotient Else dwQuotientMore = dwLeftCur \ dwRightCur dwRemainder = dwLeftCur - dwQuotientMore * dwRightCur End If If dwRemainder = DigitValue.Zero Then fResultFound = True : Exit Do fIterationIsEven = Not fIterationIsEven If dwQuotientMore < DigitValue.BitHi Then wQuotient = CUInt(dwQuotientMore) If fComputeLeftInverse Then ComputeFusedMulAdd(uLeftInvPrev, uLeftInvCur, wQuotient) If fComputeRightInverse Then ComputeFusedMulAdd(uRightInvPrev, uRightInvCur, wQuotient) Else If fComputeLeftInverse Then uTemp = uLeftInvPrev + dwQuotientMore * uLeftInvCur : uLeftInvPrev = uLeftInvCur : uLeftInvCur = uTemp End If If fComputeRightInverse Then uTemp = uRightInvPrev + dwQuotientMore * uRightInvCur : uRightInvPrev = uRightInvCur : uRightInvCur = uTemp End If End If dwLeftCur = dwRightCur : dwRightCur = dwRemainder Loop If fResultFound Then uRightCur = dwRightCur Else ' Final rounds: both numbers have only one digit now, and this digit has MS-bit unset. Dim wLeftCur As UInt32 = CUInt(dwLeftCur), wRightCur As UInt32 = CUInt(dwRightCur) Do Dim wRemainder As UInt32 = wLeftCur If (wRemainder >> nSubtractionThresholdBits) <= wRightCur Then wQuotient = DigitValue.Zero Do wQuotient += DigitValue.One : wRemainder -= wRightCur Loop While wRemainder >= wRightCur Else wQuotient = wLeftCur \ wRightCur wRemainder = wLeftCur - wQuotient * wRightCur End If If wRemainder = DigitValue.Zero Then fResultFound = True : Exit Do fIterationIsEven = Not fIterationIsEven If fComputeLeftInverse Then ComputeFusedMulAdd(uLeftInvPrev, uLeftInvCur, wQuotient) If fComputeRightInverse Then ComputeFusedMulAdd(uRightInvPrev, uRightInvCur, wQuotient) wLeftCur = wRightCur : wRightCur = wRemainder Loop uRightCur = wRightCur End If End If If fComputeLeftInverse Then uLeftInverse = If(fIterationIsEven, uRight - uLeftInvCur, uLeftInvCur) End If If fComputeRightInverse Then uRightInverse = If(fIterationIsEven, uRightInvCur, uLeft - uRightInvCur) End If Return uRightCur End Function ''' <remarks>All word-sized parameters must have their most-significant bit unset.</remarks> Private Shared Sub ComputeFusedMulMulAdd( ByRef uLeftInvPrev As BigUInteger, ByRef uLeftInvCur As BigUInteger, ByVal wLeftInvPrev As UInt32, ByVal wLeftInvCur As UInt32, ByVal wRightInvPrev As UInt32, ByVal wRightInvCur As UInt32) Dim ndxDigitMaxPrev As Integer = uLeftInvPrev.ValueLength - 1, ndxDigitMaxCur As Integer = uLeftInvCur.ValueLength - 1, ndxDigitMaxNew As Integer = ndxDigitMaxCur + 1 Dim awLeftInvPrev() As UInt32 = uLeftInvPrev.ValueDigits, awLeftInvCur() As UInt32 = uLeftInvCur.ValueDigits Dim awLeftInvPrevNew(0 To ndxDigitMaxNew) As UInt32, awLeftInvCurNew(0 To ndxDigitMaxNew) As UInt32 Dim dwResult As UInt64, wCarryLeftPrev As UInt32 = DigitValue.Zero, wCarryLeftCur As UInt32 = DigitValue.Zero Dim wDigitLeftInvPrev, wDigitLeftInvCur As UInt32 For ndxDigit As Integer = 0 To ndxDigitMaxPrev wDigitLeftInvPrev = awLeftInvPrev(ndxDigit) : wDigitLeftInvCur = awLeftInvCur(ndxDigit) dwResult = wCarryLeftPrev + wLeftInvPrev * CULng(wDigitLeftInvPrev) + wRightInvPrev * CULng(wDigitLeftInvCur) awLeftInvPrevNew(ndxDigit) = CUInt(dwResult And DigitValue.Full) : wCarryLeftPrev = CUInt(dwResult >> DigitSize.Bits) dwResult = wCarryLeftCur + wLeftInvCur * CULng(wDigitLeftInvPrev) + wRightInvCur * CULng(wDigitLeftInvCur) awLeftInvCurNew(ndxDigit) = CUInt(dwResult And DigitValue.Full) : wCarryLeftCur = CUInt(dwResult >> DigitSize.Bits) Next If ndxDigitMaxCur > ndxDigitMaxPrev Then For ndxDigit As Integer = ndxDigitMaxPrev + 1 To ndxDigitMaxCur wDigitLeftInvCur = awLeftInvCur(ndxDigit) dwResult = wCarryLeftPrev + wRightInvPrev * CULng(wDigitLeftInvCur) awLeftInvPrevNew(ndxDigit) = CUInt(dwResult And DigitValue.Full) : wCarryLeftPrev = CUInt(dwResult >> DigitSize.Bits) dwResult = wCarryLeftCur + wRightInvCur * CULng(wDigitLeftInvCur) awLeftInvCurNew(ndxDigit) = CUInt(dwResult And DigitValue.Full) : wCarryLeftCur = CUInt(dwResult >> DigitSize.Bits) Next End If If wCarryLeftPrev <> DigitValue.Zero Then awLeftInvPrevNew(ndxDigitMaxNew) = wCarryLeftPrev If wCarryLeftCur <> DigitValue.Zero Then awLeftInvCurNew(ndxDigitMaxNew) = wCarryLeftCur uLeftInvPrev = New BigUInteger(awLeftInvPrevNew) : uLeftInvCur = New BigUInteger(awLeftInvCurNew) End Sub ''' <remarks>All word-sized parameters must have their most-significant bit unset.</remarks> Private Shared Sub ComputeFusedMulMulSub( ByRef uLeftCur As BigUInteger, ByRef uRightCur As BigUInteger, ByVal wLeftInvPrev As UInt32, ByVal wLeftInvCur As UInt32, ByVal wRightInvPrev As UInt32, ByVal wRightInvCur As UInt32, ByVal fShorthandIterationIsEven As Boolean) Dim ndxDigitMax As Integer = uLeftCur.ValueLength - 1, fRightIsShorter As Boolean = (uRightCur.ValueLength < uLeftCur.ValueLength), ndxDigitStop As Integer = If(fRightIsShorter, ndxDigitMax - 1, ndxDigitMax) Dim awLeftCur() As UInt32 = uLeftCur.ValueDigits, awRightCur() As UInt32 = uRightCur.ValueDigits Dim awLeftNew(0 To ndxDigitMax) As UInt32, awRightNew(0 To ndxDigitStop) As UInt32 Dim iTemp As Int64, wCarryLeft As Int32 = 0I, wCarryRight As Int32 = 0I Dim wDigitLeftCur, wDigitRightCur As UInt32 If fShorthandIterationIsEven Then For ndxDigit As Integer = 0 To ndxDigitStop wDigitLeftCur = awLeftCur(ndxDigit) : wDigitRightCur = awRightCur(ndxDigit) iTemp = wCarryLeft + CLng(wDigitRightCur) * wRightInvPrev - CLng(wDigitLeftCur) * wLeftInvPrev awLeftNew(ndxDigit) = CUInt(iTemp And DigitValue.Full) : wCarryLeft = CInt(iTemp >> DigitSize.Bits) iTemp = wCarryRight + CLng(wDigitLeftCur) * wLeftInvCur - CLng(wDigitRightCur) * wRightInvCur awRightNew(ndxDigit) = CUInt(iTemp And DigitValue.Full) : wCarryRight = CInt(iTemp >> DigitSize.Bits) Next If fRightIsShorter Then wDigitLeftCur = awLeftCur(ndxDigitMax) iTemp = wCarryLeft - CLng(wDigitLeftCur) * wLeftInvPrev awLeftNew(ndxDigitMax) = CUInt(iTemp And DigitValue.Full) End If Else For ndxDigit As Integer = 0 To ndxDigitStop wDigitLeftCur = awLeftCur(ndxDigit) : wDigitRightCur = awRightCur(ndxDigit) iTemp = wCarryLeft + CLng(wDigitLeftCur) * wLeftInvPrev - CLng(wDigitRightCur) * wRightInvPrev awLeftNew(ndxDigit) = CUInt(iTemp And DigitValue.Full) : wCarryLeft = CInt(iTemp >> DigitSize.Bits) iTemp = wCarryRight + CLng(wDigitRightCur) * wRightInvCur - CLng(wDigitLeftCur) * wLeftInvCur awRightNew(ndxDigit) = CUInt(iTemp And DigitValue.Full) : wCarryRight = CInt(iTemp >> DigitSize.Bits) Next If fRightIsShorter Then wDigitLeftCur = awLeftCur(ndxDigitMax) iTemp = wCarryLeft + CLng(wDigitLeftCur) * wLeftInvPrev awLeftNew(ndxDigitMax) = CUInt(iTemp And DigitValue.Full) End If End If uLeftCur = New BigUInteger(awLeftNew) : uRightCur = New BigUInteger(awRightNew) End Sub ''' <remarks>All word-sized parameters must have their most-significant bit unset.</remarks> Private Shared Sub ComputeFusedMulAdd(ByRef uLeftInvPrev As BigUInteger, ByRef uLeftInvCur As BigUInteger, ByVal wQuotient As UInt32) Dim ndxDigitPrevMax As Integer = uLeftInvPrev.ValueLength - 1, ndxDigitCurMax As Integer = uLeftInvCur.ValueLength - 1, ndxDigitNewMax As Integer = ndxDigitCurMax + 1 Dim awLeftInvPrev() As UInt32 = uLeftInvPrev.ValueDigits, awLeftInvCur() As UInt32 = uLeftInvCur.ValueDigits, awLeftInvNew(0 To ndxDigitNewMax) As UInt32 Dim dwResult As UInt64 = DigitValue.Zero, wCarry As UInt32 = DigitValue.Zero For ndxDigit As Integer = 0 To ndxDigitPrevMax dwResult = CULng(wCarry) + awLeftInvPrev(ndxDigit) + CULng(wQuotient) * awLeftInvCur(ndxDigit) awLeftInvNew(ndxDigit) = CUInt(dwResult And DigitValue.Full) : wCarry = CUInt(dwResult >> DigitSize.Bits) Next For ndxDigit As Integer = ndxDigitPrevMax + 1 To ndxDigitCurMax dwResult = CULng(wCarry) + CULng(wQuotient) * awLeftInvCur(ndxDigit) awLeftInvNew(ndxDigit) = CUInt(dwResult And DigitValue.Full) : wCarry = CUInt(dwResult >> DigitSize.Bits) Next If wCarry <> DigitValue.Zero Then awLeftInvNew(ndxDigitNewMax) = wCarry uLeftInvPrev = uLeftInvCur : uLeftInvCur = New BigUInteger(awLeftInvNew) End Sub

If you want to use this code directly, you may need the Visual Basic 2012 compiler for some constructs - I have not checked previous versions; and I don’t know about the minimal version of .Net (at least 3.5 should be enough); Compiled applications are known to run on Mono, although they have poor performance. The only thing I'm absolutely sure is that you should not try to use VB-to-C # automatic translators, as they are terribly bad in such subjects; rely only on your own head.

+5
source

Source: https://habr.com/ru/post/946798/

More articles:


All Articles