求解:任意大数精简表达的方案

9 views
Skip to first unread message

快乐人生

unread,
Aug 7, 2021, 11:10:52 PM8/7/21
to szdiy
大家好,我是李银东,邮件列表里交流少了,很安静啊,我今天抛出一个话题,向大家请教和讨论

求解:任意大数精简表达的方案

一个大数有几千位数字,比较长,有什么方法把大数转换成比较短的表达,计算后又能得到原大数数值,实现大数精确而简短的表达?

例如:以下大数A有2946位数字,可以转换成:888^999,又可以根据这个表达式计算出原大数的精确数值,这就是精简表达。但这数值是个特例,是否任意大数都可以实现精简表达呢?(简短程度:表达字符数量小于大数长度的五分之一)

任意大数的精简表达,这个问题,我还不知道是否有解,是不是一个数学界的难题。在国内外网络上都搜不到对应的结果。我需要有一个函数,输入的是任意大数,输出的是精简表达的字符串,如果没有这函数,就动手造一个。我在研究解决思路,欢迎交流

上例中A如下:
291442452478250310782535603950900043573276878800339074155878174371515047907089997307989324018467987051386421242680381047034018354720248627940441757303799382783730775515182342434155181681595298734040653167112388213743173309577771537050097233595171515197985510476073214600080520886543855872656844401771995312539375986019731911073484758955581364408465109360596639270799821012607851273379731083749102415901577644715714906372201822585957315150736004336781850452514727545253843047844238329617644166346276001660706399955938501116460089032461821832198166178706146840650732952202300073978546042808324858543800243508008097774521988655822934245723910425087491613999109394381667242008252322673084836611569607195773181495155901593611070836176064365579568506812924247476501823052546586062307396352389011688060403437209895212580928367933972127232394442497650281173124641190688718368558319305977470393782385189459467469687160300605599214650109453720307006930097685642296824140142279052390734372510557685255374283105318613695532361741764444070172392561874030501162834402479559236541989819567510153665309688745744774818499539555478547039327657659774263679085485069148607990716792460218359464666183761797726076111224820682468938491218722274684863775488806522076623661958189211978426764107432137213261837822108352337031672223997930807139460210405925794981800381609932364227050939411362926678906081820334343889076837723020033223831258580220050975782627383182236781531494201480233757134445812041021654789492050636729131050449361828751413029805201061614103906721390921334589885208698898444812746662012081532572686099941201633012270806912242984655898579359091224308942155538771099060964388340762879232703157023968017158370103603278964424547931480187534765967535116416268304585118363487611462448210281778377231309169194458614587415888364545867741635618022984999702377407437640052922492784706600246698225635464942177359227615217191449062216944868886574574065982663521463351254255169191774841217110743742425197146636751035786153330100359926543186463494734179543554056334714161428043781875232595209348373896775664598178431731937377972339162681720525001794250503532375080361706141632582357289270004865650350699600937296838534731062407306417075364929717119877333231236808451709085237934416759508305797636226423535071944238196994651125162517530134340661257017542344152044604323804606822626345147117483760785877353984979557633662160472889051408044623631696508739016789521338679507731908139506602490148318603168695134722734341175896985683234257263841406018339045051922658056944858272450829923708489012190800316979010119271631550687356463836035921606575442979155952173087111874221534225341561656791990682619049102052978965872115043939907542565433650760221467641742108971758317613286491445924354143922138559938842398492211142993205134497106567870775490968053284658214915517376500774079333591090977542932915425109186343104100381734839588162426791447280043547004190035715970094333952

Nala Ginrut

unread,
Aug 7, 2021, 11:47:15 PM8/7/21
to sz...@googlegroups.com
请了解下GMP

--
--
You received this message because you are subscribed to the Google
Groups "Shenzhen DIY community" group.
To post to this group, send email to sz...@googlegroups.com
To unsubscribe from this group, send email to
szdiy+un...@googlegroups.com
For more options, visit this group at
http://www.szdiy.org
http://groups.google.com/group/szdiy?hl=zh-CN
---
您收到此邮件是因为您订阅了Google网上论坛上的“Shenzhen DIY community”群组。
要退订此群组并停止接收此群组的电子邮件,请发送电子邮件到szdiy+un...@googlegroups.com
要在网络上查看此讨论,请访问https://groups.google.com/d/msgid/szdiy/tencent_AB43ABB5EDD6C041027D976F33C21602EE05%40qq.com

快乐人生

unread,
Aug 8, 2021, 12:13:17 AM8/8/21
to szdiy
我看了GMP,它里边的函数没有实现大数精简的功能,它还是UNIX系统下开发的,在Windows中安装还有点麻烦,需要再安装UNIX模拟环境。我还没有体验过它。谁对GMP比较熟悉,它对实现大数精简表达有支持吗?


------------------ 原始邮件 ------------------
发件人: "szdiy" <nalag...@gmail.com>;
发送时间: 2021年8月8日(星期天) 中午11:47
收件人: "szdiy"<sz...@googlegroups.com>;
主题: Re: [szdiy] 求解:任意大数精简表达的方案

Liang Guo

unread,
Aug 8, 2021, 2:21:45 AM8/8/21
to sz...@googlegroups.com
不存在这样的函数,不存在这样的算法。打个比方说,如果1000位的数都能用100位的数字进行表达,由于这个算法是多对一的关系,则必定有多个1000位的原始数据映射到1个100位的数字。

不能够对所有的数字均实现这样的表达,但是可以对部分数能够用一些形式进行简化,比如你所举出的例子。

这部分知识应该是关于计算的基本理论里讨论。
> --
> --
> You received this message because you are subscribed to the Google
> Groups "Shenzhen DIY community" group.
> To post to this group, send email to sz...@googlegroups.com
> To unsubscribe from this group, send email to
> szdiy+un...@googlegroups.com
> For more options, visit this group at
> http://www.szdiy.org
> http://groups.google.com/group/szdiy?hl=zh-CN
> ---
> 您收到此邮件是因为您订阅了Google网上论坛上的“Shenzhen DIY community”群组。
> 要退订此群组并停止接收此群组的电子邮件,请发送电子邮件到szdiy+un...@googlegroups.com
> 要在网络上查看此讨论,请访问https://groups.google.com/d/msgid/szdiy/tencent_AB43ABB5EDD6C041027D976F33C21602EE05%40qq.com



--
Liang Guo

Nathan

unread,
Aug 8, 2021, 2:50:03 AM8/8/21
to sz...@googlegroups.com
质数顺序编号,非质数分解质因数


> 在 2021年8月8日,下午2:21,Liang Guo <bluesto...@gmail.com> 写道:
>
> 不存在这样的函数,不存在这样的算法。打个比方说,如果1000位的数都能用100位的数字进行表达,由于这个算法是多对一的关系,则必定有多个1000位的原始数据映射到1个100位的数字。
> 您收到此邮件是因为您订阅了 Google 网上论坛的“Shenzhen DIY community”群组。
> 要退订此群组并停止接收此群组的电子邮件,请发送电子邮件到szdiy+un...@googlegroups.com
> 要在网络上查看此讨论,请访问 https://groups.google.com/d/msgid/szdiy/CAJwrgW5SQdGZT%2BraH0gnDo0YRKOF_itU4eR33DGfcf%3D0AQpryQ%40mail.gmail.com

Nala Ginrut

unread,
Aug 8, 2021, 3:02:35 AM8/8/21
to sz...@googlegroups.com
GMP 是用来解决任意大数字的计算的,而且跨平台。
你所说的数字压缩算法,其实从实用的角度做一个hash就行了,如果担心冲突,可以了解下hash table如何解决冲突问题。另外一个思路是考虑下短网址的实现。
如果是要从数学上找出数字压缩的一般算法,我觉得希望不大。


Reply all
Reply to author
Forward
0 new messages