腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >快速傅立叶变换多项式乘法

问快速傅立叶变换多项式乘法
EN

Stack Overflow用户

提问于 2012-07-06 04:07:40

回答 1查看 1.4K关注 0票数 2

我正在使用FFT来计算某个点上的多项式，以便可以使用值表示法来表示它。(表示为与其度数相等的点数)

然而，为了将两个d次多项式相乘，我需要在2d +1点处计算这两个多项式。但是，使用FFT进行计算(乘以dth的单位根)仅计算d点处的多项式。因此，如果FFT只在d点处计算多项式，那么如何使用FFT进行多项式计算？(相对于2d + 1)

math

computer-science

fft

algorithm

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-07-06 04:24:10

你可以选择计算-1的第n个根。如果您需要2d-1点(我怀疑您需要)，只需使用-1的(2d-1)-th根。实际上，您通常会使用-1的2^k次方根，其中2^k是2log2d-1的第一次幂，因为对2的幂进行快速快速傅立叶变换要容易得多。由于O的定义允许常数因子，因此复杂度仍然是O(d >= d)。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/11355705

复制

char转换为数字_char字符转int

ascii 编程算法

刷题遇到一个考点是 char型数字转 int 进行计算的问题。一看就会，一做就错，显然是在这里的认识薄弱了。将一番搜索的结果记录下来，以备再忘来打脸。

全栈程序员站长

2022/11/10

4.1K0

python中字符串类型转换为数字类型_python字符串转int

https 网络安全编程算法

全栈程序员站长

2022/11/07

5.4K0

mysql整型转字符串_java中如何将字符串转换为字符数组

java https http 网络安全

select * from A order by cast(name as unsigned);

全栈程序员站长

2022/09/27

23.3K0

java字符串类型转换为int_java中double转int类型

html java https http 网络安全

由于double的范围比int数据类型大，所以当int值被赋给double时，java会自动将int值转换为double。

全栈程序员站长

2022/08/03

4.2K0

json字符串转换为Json对象_前端字符串转json

maven java https 网络安全编程算法

参考网上的文章，做了一个关于json的总结，进行留存帮助以后阅读，希望可以帮助到大家。

全栈程序员站长

2022/09/28

7.6K0

C语言中把数字转换为字符串【转】

其他

在将各种类型的数据构造成字符串时，sprintf 的强大功能很少会让你失望。由于sprintf 跟printf 在用法上几乎一样，只是打印的目的地不同而已，前者打印到字符串中，后者则直接在命令行上输出。这也导致sprintf 比printf 有用得多。 sprintf 是个变参函数，定义如下： int sprintf( char *buffer, const char *format [, argument] ... ); 除了前两个参数类型固定外，后面可以接任意多个参数。而它的精华，显然就在第二个参数：格式化字符串上。 printf 和sprintf 都使用格式化字符串来指定串的格式，在格式串内部使用一些以“%”开头的格式说明符（format specifications）来占据一个位置，在后边的变参列表中提供相应的变量，最终函数就会用相应位置的变量来替代那个说明符，产生一个调用者想要的字符串。格式化数字字符串 sprintf 最常见的应用之一莫过于把整数打印到字符串中，所以，spritnf 在大多数场合可以替代 itoa。如： //把整数123 打印成一个字符串保存在s 中。 sprintf(s, "%d", 123); //产生"123" 可以指定宽度，不足的左边补空格： sprintf(s, "%8d%8d", 123, 4567); //产生：" 123 4567" 当然也可以左对齐： sprintf(s, "%-8d%8d", 123, 4567); //产生："123 4567" 也可以按照16 进制打印： sprintf(s, "%8x", 4567); //小写16 进制，宽度占8 个位置，右对齐 sprintf(s, "%-8X", 4568); //大写16 进制，宽度占8 个位置，左对齐这样，一个整数的16 进制字符串就很容易得到，但我们在打印16 进制内容时，通常想要一种左边补0 的等宽格式，那该怎么做呢？很简单，在表示宽度的数字前面加个0 就可以了。 sprintf(s, "%08X", 4567); //产生："000011D7" 上面以”%d”进行的10 进制打印同样也可以使用这种左边补0 的方式。这里要注意一个符号扩展的问题：比如，假如我们想打印短整数（short）-1 的内存16 进制表示形式，在Win32 平台上，一个short 型占2 个字节，所以我们自然希望用4 个16 进制数字来打印它： short si = -1; sprintf(s, "%04X", si); 产生“FFFFFFFF”，怎么回事？因为spritnf 是个变参函数，除了前面两个参数之外，后面的参数都不是类型安全的，函数更没有办法仅仅通过一个“%X”就能得知当初函数调用前参数压栈时被压进来的到底是个4 字节的整数还是个2 字节的短整数，所以采取了统一4 字节的处理方式，导致参数压栈时做了符号扩展，扩展成了32 位的整数-1，打印时4 个位置不够了，就把32 位整数-1 的8 位16 进制都打印出来了。如果你想看si 的本来面目，那么就应该让编译器做0 扩展而不是符号扩展（扩展时二进制左边补0 而不是补符号位）： sprintf(s, "%04X", (unsigned short)si); 就可以了。或者： unsigned short si = -1; sprintf(s, "%04X", si); sprintf 和printf 还可以按8 进制打印整数字符串，使用”%o”。注意8 进制和16 进制都不会打印出负数，都是无符号的，实际上也就是变量的内部编码的直接的16 进制或8 进制表示。控制浮点数打印格式浮点数的打印和格式控制是sprintf 的又一大常用功能，浮点数使用格式符”%f”控制，默认保留小数点后6 位数字，比如： sprintf(s, "%f", 3.1415926); //产生"3.141593" 但有时我们希望自己控制打印的宽度和小数位数，这时就应该使用：”%m.nf”格式，其中m 表示打印的宽度，n 表示小数点后的位数。比如： sprintf(s, "%10.3f", 3.1415626); //产生：" 3.142" sprintf(s, "%-10.3f", 3.1415626); //产生："3.142 " sprintf(s, "%.3f", 3.1415626); //不指定总宽度，产生："3.142" 注意一个问题，你猜 int i = 100; sprintf(s, "%.2f", i); 会打出什么东东来？“100.00”？对吗？自己试试就知道了，同时也试试下面这个： sprintf(s, "%.2f", (double)i); 第一个打出来的肯定不是正确结果，原因跟前面提到的一样，参数压栈时调用者并不知道跟i相对应

用户2038589

2018/09/06

16.8K0

integer转换为string_go 字符串转int

编程算法

str := “123” // string 转 int i, err := strconv.Atoi(str) if err == nil { 　　fmt.Printf(“i: %v\n”,i) } // string 转 int64 i64,err := strconv.ParseInt(str,10,64) if err == nil { 　　fmt.Printf(“i64: %v\n”,i64) } // string 转 int32 j,err := strconv.ParseInt(str,10,32) if err == nil { 　　fmt.Printf(“i32: %v\n”,int32(j)) }

全栈程序员站长

2022/11/06

3.4K0

通过post请求api获取土味情话

api token

用的ALAPI，自己申请token填上即可。 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title>

岳泽以

2022/10/26

7370

java对象转换为json字符串_复杂json字符串转对象

网站 java javascript api xml

在学习如何编写基于Java的软件时，开发人员遇到的第一个障碍就是如何将其代码与其他软件连接。这通常是JSON的来源。虽然您可能是Java向导，但JSON是另一种动物。无论如何，这篇博客文章解释了完成工作所需的一切。

全栈程序员站长

2022/09/30

8.9K0

将字符串转换为date类型_java字符串转date类型

https 网络安全编程算法

全栈程序员站长

2022/11/09

14.1K0

python json转字符串_在python中将json转换为字符串

json https 网络安全编程算法

一开始我没有清楚地解释我的问题。在python中将json转换为字符串时，请尝试使用str()和json.dumps()。

全栈程序员站长

2022/11/16

10.3K0

js中字符串转换为数字

数据结构编程算法

js提供了parseInt()和parseFloat()两个转换函数。前者把值转换成整数，后者把值转换成浮点数。

用户7741497

2022/03/06

11.5K1

关于null通过+" "，String.ValueOf转换为字符串的问题！！！

编程算法 java jquery

起因：数据库里面建一个保存状态的字段其vachar大小为 2，当获取其他平台的返回值为null的时候通过String.valueOf()转换为字符串的时候和+" " 转换字符串出现由于字符过大保存异常。准备：查看String.valueOf()的源码：

袁新栋-jeff.yuan

2020/08/26

6110

通用的组件请求管理器，解决异步请求中的后发先到的问题

http

1.每当需要取消之前发出的请求时，需要调用clearRequestId方法。 2.在优化版本中，显式定义了两种取消请求的方法，clearFormerRequest和clearFormerRequestBeforeRequest，后者用于在发送新的请求前使用，前者是没有发送新的请求，而是通过其他操作取消了请求，比如点击取消按钮。

theanarkh

2019/03/06

9030

直接取出 post 请求中的 json、得请求体参数、查看 post 请求参数

json post

方法如下： try{ ServletRequestAttributes requestAttributes = (ServletRequestAttributes) RequestContextHolder.getRequestAttributes(); HttpServletRequest request = requestAttributes.getRequest(); StringBuffer sb = new S

微风-- 轻许--

2022/04/13

4.9K0

sqlserver日期转字符串 yyyymmddhhmmss_sql中将date转换为字符串

https 网络安全

全栈程序员站长

2022/11/09

4.8K0

Java中HttpServletRequest请求参数转Map工具类/接收HttpServletRequest请求参数转Map

map

public class MapDataUtil { public static Map<String, Object> convertDataMap(HttpServletRequest request) { Map<String, String[]> properties = request.getParameterMap(); Map<String, Object> returnMap = new HashMap<String, Object>();

目的地-Destination

2023/03/06

1.4K0

通过 Apifox Echo 了解 Content-Type 及对应的请求体编码

https 网络安全 javascript node.js api

我们在与后端接口联调中，你知道请求体可以由哪几种类型，以及对应的 Content-Type 是多少吗？

山月

2023/01/10

3K1

通过 Apifox Echo 了解 Content-Type 及对应的请求体编码

Objective-C中把URL请求的参数转换为字典

objective-c

上一篇博客中是把URL转换为字典，那么我们如何把URL请求中的参数封装成字典，然后再封装成数组呢？对OC中字符串操作熟练的小伙伴们应该觉得这是一个a+b的问题，没错把URL中的参数转换为字典主要是对字符串的截取，关键是怎么个截法，才能把字符串中的参数列表分别转换成键值对。下面是小菜自己的转换思路，如果有更好的结局方法还请批评指正，相互学习交流一下，转载请注明出处。首先我们得会一个字符串拆分函数 componentsSeparatedByString:@"&"，把字符串按照&进行拆分，然后

lizelu

2018/01/11

1.8K0

java将字符串转换为json对象的方法_java jsonobject转string

java android https 网络安全

在与服务器交互的时候，我们往往会使用json字符串，今天的例子是java对象转化为字符串，

全栈程序员站长

2022/11/08

21.2K0

相似问题

我试图从React中的对象(API)中提取数据

试图提取数据时与API的不同

读取csv数据集配置j测量仪中的变量

使用J测量仪一次测试多个API的性能

我试图从api调用中检索数据

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问快速傅立叶变换多项式乘法
EN