You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
lavos/cap3/ex19.go

137 lines
3.5 KiB

package cap3
import "strings"
// Ex19 高精度阶乘
func Ex19(n uint64) string {
result := []uint8{1}
for i := uint64(2); i <= n; i++ {
result = multiply(result, i)
}
return DigitSlice2String(result)
}
func multiply(a []uint8, b uint64) []uint8 {
result := make([]uint8, len(a)+22)
resultEndIdx := len(result) - 1
bOffset := 0
for i := b; i >= 1; i /= 10 {
carry := uint8(0)
bDigit := uint8(i % 10)
aEnd, resultIdx := len(a)-1, 0
for j := 0; j < len(a); j++ {
// 字符转数字
aDigit := a[aEnd-j]
// 当前位计算结果 = 当前结果 + aDigit*bDigit + 进位
resultIdx = resultEndIdx - (bOffset + j)
num := result[resultIdx] + aDigit*bDigit + carry
// 当前位为计算结果的个位,进位为十位上的数字
result[resultIdx] = num % 10
carry = num / 10
}
// 如果还有进位,则对下一个结果位添加进位,此时不会再有进位
if carry != 0 {
resultIdx--
result[resultIdx] += carry
}
bOffset++
}
return result
}
func multiply2(a []uint8, b uint64) []uint8 {
result := make([]uint8, len(a)+22)
resultEndIdx := len(result)*2 - 1
bOffset := 0
for i := b; i >= 1; i /= 10 {
carry := uint8(0)
bDigit := uint8(i % 10)
aEnd, resultIdx := len(a)*2-1, 0
for j := 0; j < len(a); j++ {
// 字符转数字
aDigit := uint8(0)
// 4,5 -> 37(0010,0101)
aIdx := aEnd - j
if aIdx%2 == 0 {
aDigit = a[aIdx/2] >> 4
} else {
aDigit = a[aIdx/2] & 0b00001111
}
// 当前位计算结果 = 当前结果 + aDigit*bDigit + 进位
resultIdx = resultEndIdx - (bOffset + j)
bitIdx := resultIdx / 2
if resultIdx%2 == 0 {
num := (result[bitIdx] >> 4) + aDigit*bDigit + carry
// 清位
// 4,5 -> 37(0010,0101) => 0,5 -> 5(0000,0101)
result[bitIdx] &= 0b00001111
// 位赋值
// 0,5 -> 5(0000,0101) => 5,5 -> 5(0101,0101)
// 5(0000,0101) << 4 => 80(0101,0000)
// 5(0000,0101) | 80(0101,0000) => 5,5 -> 5(0101,0101)
result[bitIdx] |= (num % 10) << 4
carry = num / 10
} else {
num := (result[bitIdx] & 0b00001111) + aDigit*bDigit + carry
// 清位
// 4,5 -> 37(0010,0101) => 4,0 -> 32(0010,0000)
result[bitIdx] &= 0b11110000
// 赋值
// 4,0 -> 32(0010,0000) => 4,5 -> 37(0010,0101)
// 32(0010,0000) | 5(0000,0101) => 4,5 -> 37(0010,0101)
result[bitIdx] |= num % 10
carry = num / 10
}
}
// 如果还有进位,则对下一个结果位添加进位,此时不会再有进位
if carry != 0 {
resultIdx--
bitIdx := resultIdx / 2
if resultIdx%2 == 0 {
// 4,5 -> 37(0010,0101) => 5,5 -> 37(0101,0101)
// 4+1 -> 5(0000,0101) << 4 => 80(0101,0000)
// 5(0000,0101) | 80(0101,0000) => 5,5 -> 5(0101,0101)
result[bitIdx] &= 0b00001111
num := (result[bitIdx] >> 4) + carry
result[bitIdx] |= num << 4
} else {
result[bitIdx] &= 0b11110000
num := (result[bitIdx] & 0b00001111) + carry
result[bitIdx] |= num
}
}
bOffset++
}
return result
}
// Ex19LowMem 低内存使用版,两位数字结果按位存在同一个uint8中,一个0~9数字只使用四字节,uint8可存两位,一个字节拆成两半用
func Ex19LowMem(n uint64) string {
result := []uint8{1}
for i := uint64(2); i <= n; i++ {
result = multiply2(result, i)
}
zeroPrefix := true
sb := strings.Builder{}
for _, num := range result {
if zeroPrefix && num == 0 {
continue
} else {
zeroPrefix = false
}
sb.WriteByte((num >> 4) + 48)
sb.WriteByte((num & 0b00001111) + 48)
}
return sb.String()
}