網(wǎng)站首頁 編程語言 正文
前言
由于上一章《C/C++ 高精度（加減乘除）算法簡單實現(xiàn)》實現(xiàn)了基本的高精度計算，數(shù)組的每個元素存儲一位10進制的數(shù)字。這樣的存儲方式并不是最優(yōu)的，32位的整型其實至少可以存儲9位高精度數(shù)字，數(shù)組元素存儲更多的位數(shù)就是壓位優(yōu)化。本文將展示壓位優(yōu)化的原理以及壓9位的實現(xiàn)和性能對比。
一、基本原理
1、存儲方式
壓位優(yōu)化就是將原本存儲一位的數(shù)組元素變成存儲多位，這樣就可以提升運算效率，通常最高能存儲9位，如下圖示例為存儲4位。
2、計算方式
采用模擬立豎式計算，比如加法的計算流程，如下圖所示，20481024+80001000=100482024：
二、完整代碼
因為接口以及使用方法與上一章《C/C++ 高精度（加減乘除）算法簡單實現(xiàn)》是完全一致的，所以這里直接展示完整代碼，省略使用示例。下面代碼為壓9位實現(xiàn)。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdint.h>
/// <summary>
/// 通過字符串初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]字符串首地址</param>
static void loadStr(int* a, const char* value) {
int len = strlen(value);
int left = len % 9;
char s[8], * p = (char*)value + left;
a[0] = ceil(len / 9.0);
len = len / 9.0;
for (int i = 1; i <= len; i++)
sscanf(p + (len - i ) * 9, "%09d", &a[i]);
if (left){
sprintf(s, "%%0%dd", left);
sscanf(value, s, &a[a[0]]);
}
}
/// <summary>
/// 輸出到字符串，
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="str">[out]字符串，由外部停供緩沖區(qū)，需要保證長度足夠</param>
static void toStr(int* a, char* str) {
if (!a[0]) {
sprintf(str, "0");
return;
}
sprintf(str, "%d", a[a[0]]);
str += strlen(str);
for (int i = a[0]-1; i > 0; i--)
sprintf(str +( a[0] -i-1)*9, "%09d", a[i]);
str[(a[0]-1)*9] = '\0';
}
/// <summary>
/// 通過無符號整型初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]整型值</param>
static void loadInt(int* a, uint64_t value) {
a[0] = 0;
while (value)a[++a[0]] = value % 1000000000, value /= 1000000000;
}
/// <summary>
/// 比較兩個高精度數(shù)的大小
/// </summary>
/// <param name="a">[in]第一個數(shù)</param>
/// <param name="b">[in]第二個數(shù)</param>
/// <returns>1是a>b,0是a==b,-1是a<b</returns>
static int compare(int* a, int* b) {
if (a[0] > b[0])return 1;
if (a[0] < b[0])return -1;
for (int i = a[0]; i > 0; i--)
if (a[i] > b[i])return 1;
else if (a[i] < b[i])return -1;
return 0;
}
/// <summary>
/// 復制
/// </summary>
/// <param name="a">[in]源</param>
/// <param name="b">[in]目標</param>
static void copy(int* a, int* b) {
memcpy(b, a, (a[0] + 1) * sizeof(int));
}
/// <summary>
/// 打印輸出結(jié)果
/// </summary>
static void print(int* a) {
int i = a[0];
printf("%d", a[i--]);
for (; i > 0; i--)printf("%09d", a[i]);
}
/// <summary>
/// 加
/// </summary>
/// <param name="a">[in]被加數(shù)</param>
/// <param name="b">[in]加數(shù)</param>
/// <param name="c">[out]結(jié)果</param>
static void plus(int* a, int* b, int* c) {
int* p;
if (a[0] < b[0])p = a, a = b, b = p;//確保a長度最大
int i = 1, alen = a[0], blen = b[0];
c[0] = c[alen + 1] = 0;
if (a != c)memcpy(c + blen + 1, a + blen + 1, (alen - blen) * sizeof(int));//a多出的部分直接拷貝到結(jié)果
for (; i <= blen; i++) {
c[i] = a[i] + b[i];
if (c[i - 1] >= 1000000000)c[i - 1] -= 1000000000, c[i]++;//判斷上一位是否進位
}
i--;
while (c[i++] >= 1000000000)c[i - 1] -= 1000000000, c[i]++;//繼續(xù)判斷進位
c[0] = c[alen + 1] ? alen + 1 : alen;//記錄長度
}
/// <summary>
/// 加等于
///結(jié)果會保存在a中
/// </summary>
/// <param name="a">[in]被加數(shù)</param>
/// <param name="b">[in]加數(shù)</param>
static void plusq(int* a, int* b) {
plus(a, b, a);
}
/// <summary>
/// 減
/// </summary>
/// <param name="a">[in]被減數(shù),被減數(shù)必須大于等于減數(shù)</param>
/// <param name="b">[in]減數(shù)</param>
/// <param name="c">[out]結(jié)果</param>
static void sub(int* a, int* b, int* c) {
int i = 1, alen = a[0];
if (a != c)memcpy(c + b[0] + 1, a + b[0] + 1, (a[0] - b[0]) * sizeof(int));//a多出的部分直接拷貝到結(jié)果
c[0] = 1;
for (; i <= b[0]; i++) {
c[i] = a[i] - b[i];
if (c[i - 1] < 0)c[i - 1] += 1000000000, c[i] --;//判斷上一位是否補位
}
i--;
while (c[i++] < 0)c[i - 1] += 1000000000, c[i]--;//繼續(xù)判斷補位
while (!c[alen--]); c[0] = alen + 1;//記錄長度
}
/// <summary>
/// 減法等于
///結(jié)果會保存在a中
/// </summary>
/// <param name="a">[in]被減數(shù)，被減數(shù)必須大于等于減數(shù)</param>
/// <param name="b">[in]減數(shù)</param>
static void subq(int* a, int* b) {
sub(a, b, a);
}
/// <summary>
/// 乘
/// </summary>
/// <param name="a">[in]被乘數(shù)</param>
/// <param name="b">[in]乘數(shù)</param>
/// <param name="c">[out]結(jié)果，數(shù)組長度必須大于等于aLen+bLen+1</param>
static void mul(int* a, int* b, int c[]) {
int len = a[0] + b[0], d = 0;
memset(c, 0, sizeof(int) * (len + 1));
b[b[0] + 1] = 0; c[0] = 1;//防止越界
for (int i = 1; i <= a[0]; i++)
for (int j = 1; j <= b[0] + 1; j++){
int64_t t = (int64_t)a[i] * b[j] + c[j + i - 1] + d;
c[j + i - 1] = t % 1000000000;
d = t / 1000000000;
}
while (!c[len])len--; c[0] = len;
}
/// <summary>
/// 乘等于
/// 累乘,結(jié)果存放于a
/// </summary>
/// <param name="a">[in]被乘數(shù)，數(shù)組長度必須大于等于2aLen+bLen+1</param>
/// <param name="b">[in]乘數(shù)</param>
static void mulq(int* a, int* b) {
int* c = a + a[0] + b[0] + 1;
memcpy(c, a, (a[0] + 1) * sizeof(int));
mul(c, b, a);
}
/// <summary>
/// 除法
/// 依賴減法subq
/// </summary>
/// <param name="a">[in]被除數(shù),被除數(shù)必須大于除數(shù)</param>
/// <param name="b">[in]除數(shù)</param>
/// <param name="c">[out]商，數(shù)組長度大于等于3aLen-bLen+1</param>
/// <param name="mod">[out]余數(shù)，可以為NULL，數(shù)組長度大于等于aLen</param>>
static void div(int* a, int* b, int* c, int* mod) {
int len = a[0] - b[0] + 1, times, hTimes[32], * temp = c + a[0] + 1;
if (!mod)mod = temp + 2*(a[0] + 1)+1;//緩沖區(qū)
memcpy(mod, a, (a[0] + 1) * sizeof(int));
memset(c, 0, sizeof(int) * (len + 1));
memset(temp, 0, sizeof(int) * len);
c[0] = 1;//防止while越界
for (int i = len; i > 0; i--) {
memcpy(temp + i, b + 1, sizeof(int) * b[0]);//升階
temp[0] = b[0] + i - 1;
while (compare(mod, temp) != -1) {
if (times = (mod[mod[0]] * ((mod[0] - temp[0]) ? 1000000000ll : 1)) / (temp[temp[0]] + (temp[0] == 1 ? 0 : 1)))//升倍數(shù)
{
loadInt(hTimes,times);
mulq(temp, hTimes);
}
else times = 1;
while (compare(mod, temp) != -1)subq(mod, temp), c[i] += times; //減法
memcpy(temp + i, b + 1, sizeof(int) * b[0]);//還原
temp[0] = b[0] + i - 1;
}
}
while (!c[len])len--; c[0] = len;
}
/// <summary>
/// 除等于
/// 商保存在a
/// 依賴div
/// </summary>
/// <param name="a">[in]被除數(shù),被除數(shù)必須大于除數(shù)</param>
/// <param name="b">[in]除數(shù)</param>
/// <param name="mod">[out]余數(shù)，可以為NULL，數(shù)組長度大于等于aLen</param>>
static void divq(int* a, int* b, int* mod) {
div(a, b, a, mod);
}
三、性能對比
測試平臺：Windows 11
測試設備：i7 8750h
測試方式：測試5次取均值
表1、測試用例
| 測試用例 | 描述 |
|---|---|
| 1 | 整型范圍數(shù)字計算500000次 |
| 2 | 長數(shù)字與整型范圍數(shù)字計算500000次 |
| 3 | 長數(shù)字與長數(shù)字計算500000次 |
基于上述用例編寫程序進行測試，測試結(jié)果如下表
表2、測試結(jié)果
| 計算 | 測試用例 | 1位實現(xiàn)（上一章）耗時 | 9位優(yōu)化（本章）耗時 |
|---|---|---|---|
| 加法 | 測試用例1 | 0.003926s | 0.002620s |
| 加法 | 測試用例2 | 0.026735s | 0.005711s |
| 加法 | 測試用例3 | 0.029378s | 0.005384s |
| 累加 | 測試用例1 | 0.003255s | 0.002536s |
| 累加 | 測試用例2 | 0.017843s | 0.002592s |
| 累加 | 測試用例3 | 0.034025s | 0.006474s |
| 減法 | 測試用例1 | 0.004237s | 0.002078s |
| 減法 | 測試用例2 | 0.024775s | 0.004939s |
| 減法 | 測試用例3 | 0.027634s | 0.004929s |
| 累減 | 測試用例1 | 0.004272s | 0.002034s |
| 累減 | 測試用例2 | 0.005407 | 0.001942s |
| 累減 | 測試用例3 | 0.019363s | 0.004282s |
| 乘法 | 測試用例1 | 0.043608s | 0.004751s |
| 乘法 | 測試用例2 | 0.479071s | 0.028358s |
| 乘法 | 測試用例3 | 3.375447s | 0.064259s |
| 累乘 | 測試用例1 只計算1000次 | 0.001237s | 0.000137s |
| 累乘 | 測試用例2 只計算1000次 | 0.001577s | 0.000187s |
| 累乘 | 測試用例3 只計算1000次 | 5.792887s | 0.081988s |
| 除法 | 測試用例1 | 0.025391s | 0.024763s |
| 除法 | 測試用例2 | 5.292809s | 0.516090s |
| 除法 | 測試用例3 | 0.395773s | 0.073812s |
| 累除 | 測試用例1 只計算1000次 | 0.059054s | 0.035722s |
| 累除 | 測試用例2 只計算1000次 | 0.103727s | 0.060936s |
| 累除 | 測試用例3 只計算1000次 | 89.748837s | 25.126072s |
將上表數(shù)據(jù)進行分類相同類型取均值計算出提升速度如下圖所示，僅作參考。
圖1、速度提升
總結(jié)
以上就是今天要講的內(nèi)容，壓位優(yōu)化性能提升是比較顯著的，而且實現(xiàn)也很容易，大部分邏輯是一致的只是底數(shù)變大了而已。從性能測試結(jié)果來看所有計算至少由4倍的提升，乘法性能提升較大有可能是測試方法不嚴重，這個待以后驗證。總的來說，對高精度運算進行壓位優(yōu)化還是很有必要的，尤其是對時間和空間有要求的場景還是比較適用的。
附錄 1、性能測試代碼
#include<Windows.h>
#include <iostream>
static int a[819200];
static int b[819200];
static int c[819200];
static int mod[819200];
static char str[81920];
/// <summary>
/// 返回當前時間
/// </summary>
/// <returns>當前時間，單位秒，精度微秒</returns>
static double getCurrentTime()
{
LARGE_INTEGER ticks, Frequency;
QueryPerformanceFrequency(&Frequency);
QueryPerformanceCounter(&ticks);
return (double)ticks.QuadPart / (double)Frequency.QuadPart;
}
/// <summary>
/// 性能測試
/// </summary>
static void test() {
double d = getCurrentTime();
loadStr(a, "50000");
loadInt(b, 50000);
for (int64_t i = 1; i <= 500000; i++) {
plus(a, b, c);
}
printf("plus performence 1: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadInt(b, 5);
for (int64_t i = 1; i <= 500000; i++) {
plus(a, b, c);
}
printf("plus performence 2: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadStr(b, "11111111111111111111111111111111111111");
for (int64_t i = 1; i <= 500000; i++) {
plus(b, a, c);
}
printf("plus performence 3: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "50000");
loadInt(b, 50000);
for (int64_t i = 1; i <= 500000; i++) {
plusq(a, b);
}
printf("plusq performence 1: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
for (int64_t i = 500000000; i <= 500000000 + 500000; i++) {
loadInt(b, i);
plusq(a, b);
}
printf("plusq performence 2: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(b, "999999999999999999999999999999999999999999999999999999999999999999");
for (int64_t i = 500000000; i <= 500000000 + 500000; i++) {
loadInt(a, i);
plusq(a, b);
}
printf("plusq performence 3: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "50000");
loadInt(b, 10000);
for (int64_t i = 1; i <= 500000; i++) {
sub(a, b, c);
}
printf("sub performence 1: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
loadInt(b, 11111);
for (int64_t i = 1; i <= 500000; i++) {
sub(a, b, c);
}
printf("sub performence 2: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
loadStr(b, "11111111111111111111111111111111111111");
for (int64_t i = 1; i <= 500000; i++) {
sub(a, b, c);
}
printf("sub performence 3: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "50000000000");
loadInt(b, 500000);
for (int64_t i = 1; i <= 500000; i++) {
subq(a, b);
}
printf("subq performence 1: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
loadInt(b, 11111);
for (int64_t i = 1; i <= 500000; i++) {
subq(a, b);
}
printf("subq performence 2: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
loadStr(b, "11111111111111111111111111111111111111");
for (int64_t i = 1; i <= 500000; i++) {
subq(a, b);
}
printf("subq performence 3: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "50000");
loadInt(b, 12345);
for (int64_t i = 1; i <= 500000; i++) {
mul(a, b, c);
}
printf("mul performence 1: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadInt(b, 12345);
for (int64_t i = 1; i <= 500000; i++) {
mul(a, b, c);
}
printf("mul performence 2: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadStr(b, "11111111111111111111111111111111111111");
for (int64_t i = 1; i <= 500000; i++) {
mul(b, a, c);
}
printf("mul performence 3: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "2");
loadInt(b, 2);
for (int64_t i = 1; i <= 1000; i++) {
mulq(a, b);
}
printf("mulq performence 1: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadInt(b, 2);
for (int64_t i = 1; i <= 1000; i++) {
mulq(a, b);
}
printf("mulq performence 2: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadStr(b, "11111111111111111111111111111111111111");
for (int64_t i = 1; i <= 1000; i++) {
mulq(b, a);
}
printf("mulq performence 3: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "50000");
loadInt(b, 12345);
for (int64_t i = 1; i <= 500000; i++) {
div(a, b, c, mod);
}
printf("div performence 1: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
loadInt(b, 12345);
for (int64_t i = 1; i <= 500000; i++) {
div(a, b, c, NULL);
}
printf("div performence 2: %llfs\n", getCurrentTime() - d);
d = getCurrentTime();
loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
loadStr(b, "11111111111111111111111111111111111111");
for (int64_t i = 1; i <= 500000; i++) {
div(a, b, c, mod);
}
printf("div performence 3: %llfs\n", getCurrentTime() - d);
loadStr(a, "1");
loadStr(b, "2");
for (int64_t i = 1; i <= 1000; i++) {
mulq(a, b);
}
d = getCurrentTime();
for (int64_t i = 1; i <= 1000; i++) {
divq(a, b, mod);
}
printf("divq performence 1: %llfs\n", getCurrentTime() - d);
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadStr(b, "2");
for (int64_t i = 1; i <= 1000; i++) {
mulq(a, b);
}
d = getCurrentTime();
for (int64_t i = 1; i <= 1000; i++) {
divq(a, b, mod);
}
printf("divq performence 2: %llfs\n", getCurrentTime() - d);
loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
loadStr(b, "11111111111111111111111111111111111111");
for (int64_t i = 1; i <= 500; i++) {
mulq(a, b);
}
d = getCurrentTime();
for (int64_t i = 1; i <= 500; i++) {
divq(a, b, mod);
}
printf("divq performence 3: %llfs\n", getCurrentTime() - d);
}
原文鏈接：https://blog.csdn.net/u013113678/article/details/128611361
相關(guān)推薦
- 2023-04-26 C語言函數(shù)調(diào)用基礎(chǔ)應用詳解_C 語言
- 2022-11-27 Oracle?中檢查臨時表空間的方法_oracle
- 2023-11-20 Linux/樹莓派如何限制CPU使用率？cpulimit的基本用法
- 2023-12-15 Linux系統(tǒng)設置多個IP地址、默認路由、指定路由、永久刪除默認路由
- 2022-08-15 對稱式加密和非對稱加密的對比
- 2022-11-14 正則表達式手冊以備平時自己看
- 2022-04-01 用C語言實現(xiàn)推箱子游戲?qū)嵗齙C 語言
- 2022-06-23 C語言一看就懂的選擇與循環(huán)語句及函數(shù)介紹_C 語言
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學習環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速