고정 소수점 곱셈에서 오버플로 감지

Question

짧은 버전 : 부호가있는 유형의 here으로 설명 된 고정 소수점 곱셈을 사용하여 오버플로를 감지하려면 어떻게해야합니까?

긴 버전 :

나는 여전히 내 Q31.32 fixed point type 일부 오버 플로우 문제가 있습니다. 종이에 예제를 더 쉽게 적용 할 수 있도록 동일한 알고리즘 인 sbyte를 기반으로 한 Q3.4를 사용하여 훨씬 더 작은 유형을 만들었습니다. Q3.4 유형의 모든 꼬임을 해결할 수 있다면 동일한 논리가 Q31.32 유형에 적용되어야한다고 생각합니다.

16 비트 정수에서 수행하여 Q3.4 곱셈을 매우 쉽게 구현할 수 있지만 Q31.32에 128이 필요하기 때문에 존재하지 않는 것처럼 처리하고 있습니다. 존재하지 않는 비트 정수 (BigInteger가 너무 느림).

오버플로가 발생할 때 오버플로를 처리하는 곱셈을 원한다. 결과는 피연산자의 부호에 따라 표현 될 수있는 가장 큰 값 또는 가장 작은 값이다.

public static Fix8 operator *(Fix8 x, Fix8 y) { 
     sbyte xl = x.m_rawValue; 
     sbyte yl = y.m_rawValue; 

     // split x and y into their highest and lowest 4 bits 
     byte xlo = (byte)(xl & 0x0F); 
     sbyte xhi = (sbyte)(xl >> 4); 
     byte ylo = (byte)(yl & 0x0F); 
     sbyte yhi = (sbyte)(yl >> 4); 

     // perform cross-multiplications 
     byte lolo = (byte)(xlo * ylo); 
     sbyte lohi = (sbyte)((sbyte)xlo * yhi); 
     sbyte hilo = (sbyte)(xhi * (sbyte)ylo); 
     sbyte hihi = (sbyte)(xhi * yhi); 

     // shift results as appropriate 
     byte loResult = (byte)(lolo >> 4); 
     sbyte midResult1 = lohi; 
     sbyte midResult2 = hilo; 
     sbyte hiResult = (sbyte)(hihi << 4); 

     // add everything 
     sbyte sum = (sbyte)((sbyte)loResult + midResult1 + midResult2 + hiResult); 

     // if the top 4 bits of hihi (unused in the result) are neither all 0s or 1s, 
     // then this means the result overflowed. 
     sbyte topCarry = (sbyte)(hihi >> 4); 
     bool opSignsEqual = ((xl^yl) & sbyte.MinValue) == 0; 
     if (topCarry != 0 && topCarry != -1) { 
      return opSignsEqual ? MaxValue : MinValue; 
     } 

     // if signs of operands are equal and sign of result is negative, 
     // then multiplication overflowed upwards 
     // the reverse is also true 
     if (opSignsEqual) { 
      if (sum < 0) { 
       return MaxValue; 
      } 
     } 
     else { 
      if (sum > 0) { 
       return MinValue; 
      } 
     } 

     return new Fix8(sum); 
    } 

이 유형의 정밀도 내에서 정확한 결과를 제공하고 대부분의 오버 플로우를 처리합니다

이 기본적으로 유형이 표시되는 방법은 다음과 같습니다

struct Fix8 { 
    sbyte m_rawValue; 
    public static readonly Fix8 One = new Fix8(1 << 4); 
    public static readonly Fix8 MinValue = new Fix8(sbyte.MinValue); 
    public static readonly Fix8 MaxValue = new Fix8(sbyte.MaxValue); 

    Fix8(sbyte value) { 
     m_rawValue = value; 
    } 

    public static explicit operator decimal(Fix8 value) { 
     return (decimal)value.m_rawValue/One.m_rawValue; 
    } 

    public static explicit operator Fix8(decimal value) { 
     var nearestExact = Math.Round(value * 16m) * 0.0625m; 
     return new Fix8((sbyte)(nearestExact * One.m_rawValue)); 
    } 
} 

그리고 이것은 내가 현재 곱셈을 처리하는 방법입니다 사례. 그러나 다음과 같은 것은 처리하지 않습니다.

Failed -8 * 2 : expected -8 but got 0 
Failed 3.5 * 5 : expected 7,9375 but got 1,5 

첫 번째 경우에는 곱셈이 어떻게 발생하는지 알아 보겠습니다.

-8 and 2 are represented as x = 0x80 and y = 0x20. 
xlo = 0x80 & 0x0F = 0x00 
xhi = 0x80 >> 4 = 0xf8 
ylo = 0x20 & 0x0F = 0x00 
yhi = 0x20 >> 4 = 0x02 

lolo = xlo * ylo = 0x00 
lohi = xlo * yhi = 0x00 
hilo = xhi * ylo = 0x00 
hihi = xhi * yhi = 0xf0 

합은 모든 용어 hihi위한 저장 0이기 때문에 0 분명하지만 hihi의 최하위 4 비트가 최종 합에 사용된다.

내 일반적인 오버플로 감지 마법은 작동하지 않습니다. 결과는 0이므로 결과의 부호는 의미가 없습니다 (예 : 0.0625 * -0.0625 == 0 (반올림하여), 0은 양수이지만 피연산자의 부호는 다릅니다.); 또한 hihi의 상위 비트는 1111이며 오버플로가없는 경우에도 자주 발생합니다.

기본적으로 여기서 오버플로가 발생했는지 감지하는 방법을 모르겠습니다. 좀 더 일반적인 방법이 있습니까?

Answer 1

이것은 오랜 시간이 걸렸지 만, 결국 모든 것을 알아 냈습니다. 이 코드는 sbyte가 허용하는 범위에서 x와 y의 가능한 모든 조합에 대해 작동하도록 테스트되었습니다.

static sbyte AddOverflowHelper(sbyte x, sbyte y, ref bool overflow) { 
     var sum = (sbyte)(x + y); 
     // x + y overflows if sign(x)^sign(y) != sign(sum) 
     overflow |= ((x^y^sum) & sbyte.MinValue) != 0; 
     return sum; 
    } 

    /// <summary> 
    /// Multiplies two Fix8 numbers. 
    /// Deals with overflow by saturation. 
    /// </summary> 
    public static Fix8 operator *(Fix8 x, Fix8 y) { 
     // Using the cross-multiplication algorithm, for learning purposes. 
     // It would be both trivial and much faster to use an Int16, but this technique 
     // won't work for a Fix64, since there's no Int128 or equivalent (and BigInteger is too slow). 

     sbyte xl = x.m_rawValue; 
     sbyte yl = y.m_rawValue; 

     byte xlo = (byte)(xl & 0x0F); 
     sbyte xhi = (sbyte)(xl >> 4); 
     byte ylo = (byte)(yl & 0x0F); 
     sbyte yhi = (sbyte)(yl >> 4); 

     byte lolo = (byte)(xlo * ylo); 
     sbyte lohi = (sbyte)((sbyte)xlo * yhi); 
     sbyte hilo = (sbyte)(xhi * (sbyte)ylo); 
     sbyte hihi = (sbyte)(xhi * yhi); 

     byte loResult = (byte)(lolo >> 4); 
     sbyte midResult1 = lohi; 
     sbyte midResult2 = hilo; 
     sbyte hiResult = (sbyte)(hihi << 4); 

     bool overflow = false; 
     // Check for overflow at each step of the sum, if it happens overflow will be true 
     sbyte sum = AddOverflowHelper((sbyte)loResult, midResult1, ref overflow); 
     sum = AddOverflowHelper(sum, midResult2, ref overflow); 
     sum = AddOverflowHelper(sum, hiResult, ref overflow); 

     bool opSignsEqual = ((xl^yl) & sbyte.MinValue) == 0; 

     // if signs of operands are equal and sign of result is negative, 
     // then multiplication overflowed positively 
     // the reverse is also true 
     if (opSignsEqual) { 
      if (sum < 0 || (overflow && xl > 0)) { 
       return MaxValue; 
      } 
     } 
     else { 
      if (sum > 0) { 
       return MinValue; 
      } 
      // If signs differ, both operands' magnitudes are greater than 1, 
      // and the result is greater than the negative operand, then there was negative overflow. 
      sbyte posOp, negOp; 
      if (xl > yl) { 
       posOp = xl; 
       negOp = yl; 
      } 
      else { 
       posOp = yl; 
       negOp = xl; 
      } 
      if (sum > negOp && negOp < -(1 << 4) && posOp > (1 << 4)) { 
       return MinValue; 
      } 
     } 

     // if the top 4 bits of hihi (unused in the result) are neither all 0s nor 1s, 
     // then this means the result overflowed. 
     sbyte topCarry = (sbyte)(hihi >> 4); 
     // -17 (-1.0625) is a problematic value which never causes overflow but messes up the carry bits 
     if (topCarry != 0 && topCarry != -1 && xl != -17 && yl != -17) { 
      return opSignsEqual ? MaxValue : MinValue; 
     } 

     // Round up if necessary, but don't overflow 
     var lowCarry = (byte)(lolo << 4); 
     if (lowCarry >= 0x80 && sum < sbyte.MaxValue) { 
      ++sum; 
     } 

     return new Fix8(sum); 
    } 

내가 제대로 단위 .NET에 대한 테스트 고정 소수점 수학 라이브러리에 모두 함께 이러는거야, 여기에 사용할 수 있습니다 : 다음은 주석 코드 https://github.com/asik/FixedMath.Net

Answer 2

hihi을 검사하여 결과 범위 밖에있는 관련 비트가 포함되어 있는지 확인해야합니다. 또한 결과의 최상위 비트와 hihi의 해당 비트를 비교하여 캐리가 멀리 전파되었는지 여부를 확인할 수 있으며, 수행 한 경우 (즉 비트가 변경된 경우) 오버플로인지 여부를 나타낼 수 있습니다 (즉, 비트가 잘못된 방향으로 변경됨).). 이 모든 것은 보충 표기법을 사용하는 경우 공식화하는 것이 더 쉬우 며 부호 비트를 개별적으로 처리합니다. 그러나이 경우에 -8의 예는 무의미합니다.

예제를 보면 hihi = 0xf0입니다.

hihi 11110000 
result  ±###.#### 

그래서 오버 플로우 혼자 hihi에 없었다,이 경우, 경우 첫 번째 5 비트는 모두 같은 것, 결과의 부호는 hihi의 기호를 일치합니다. 이것은 여기에 해당하지 않습니다.한 번에 하나의 결과를 추가 피가수 각 단계 후 일반적인 플로우 검출을 수행하여 아마도 가장 쉽게 검출 될 수 hihi로

if ((hihi & 0x08) * 0x1f != (hihi & 0xf8)) 
    handle_overflow(); 

캐리를 이용하여이를 확인할 수있다. 그 준비를위한 멋진 코드 조각이 없습니다.