{"entities":{"Q1123580":{"pageid":1134329,"ns":120,"title":"Item:Q1123580","lastrevid":67050963,"modified":"2026-04-12T14:36:20Z","type":"item","id":"Q1123580","labels":{"en":{"language":"en","value":"Fast Fourier transformation based on number theoretic transforms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110059"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$0620048B-A904-43D6-B9D6-60207B71435A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"020e33bcd290b300992d09fbdc290e690ddd63eb","datavalue":{"value":{"text":"Fast Fourier transformation based on number theoretic transforms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123580$14D1C2BE-5701-4F4E-B49C-23EE1986BF58","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"019a78934240b36bd1d9e00d3f003f1ffc288b35","datavalue":{"value":"0677.65144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123580$4873177C-2C31-4A94-A6E0-6A7A0FA9769F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7c9ea227fc5beb09ba3eae497e7f8b7ff7e152af","datavalue":{"value":"10.1016/0016-0032(88)90031-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123580$07DC6DDF-4F61-4236-B9BD-9C1F5F85C905","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d883fd3932ba38385d7ded8638a680216be3147","datavalue":{"value":{"entity-type":"item","numeric-id":1123579,"id":"Q1123579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$47687890-83C1-4518-AE10-75103F976E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"baef6607051e1c1fa159d6f55f29297359942b74","datavalue":{"value":{"entity-type":"item","numeric-id":163037,"id":"Q163037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$9CE08201-3B01-4077-A4F5-B751A61F212D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a51b97a52c84c260f189b05761c3359b0f8838c1","datavalue":{"value":{"entity-type":"item","numeric-id":164292,"id":"Q164292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$572D681D-2A82-4257-AA24-D8268B184C1C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1123580$975BC2E2-B9E4-46C1-B54C-8BF2890C02FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bbeabc90189f816fafaa1b669c9228647343fa5e","datavalue":{"value":"A technique, denoted as FFT/NTT \\((FFT=fast\\) Fourier transform, \\(NTT=number\\) theoretic transform), is proposed for the fast computation of DFT (discrete Fourier transform) of a real sequence with prime length \\(p=2^ M+1\\). This technique is essentially a modification of \\textit{Rader}'s method [Proc. IEEE, Vol. 56, No.6, 1107-1108 (1968)] where DFT is computed via the cyclic convolution of size \\(2^ M\\) of a real sequence \\(\\{\\) a(n)\\(\\}\\) and a complex sequence \\(\\{b'(n)\\}=\\{b_ r')\\}+j\\{b_ i'(n)\\}\\), \\(j=\\sqrt{-1}\\). Then normalization and quantization by \\(a(n)=NINT[a'(n)\\cdot NORM]\\) and \\(b_ r(n)+jb_ i(n)=NINT[b'(n)\\cdot NORM]\\) is performed (NORM is the scaling factor and NINT[\\(\\cdot]\\) takes the nearest integer).    Consequently two cyclic integer convolutions \\(\\{a(n)\\}\\cdot \\{b_ r(n)\\}\\) and \\(\\{a(n)\\}\\cdot \\{b_ i(n)\\}\\) are obtained which, due to the symmetry \\(b_ r(n+N/2)=b_ r(n)\\) and \\(b_ i(n+N/2)=-b_ i(n)\\), may be accomplished in parallel (as if computing \\(\\{a(n)\\}*(\\{b_ r(n)\\}+\\{b_ i(n)\\}))\\) and without bit reversal, when using two FORTRAN subroutines supplied in the appendix, one being the direct decimation-in-frequency NTT, the other the inverse decimation-in-time NTT (reviewer's cursory check on the code listing revealed a few errors). The use of the Chinese remainder theorem is suggested whenever a large NTT modulus is necessary. A graph shows the error versus values of NORM varying from 1000 to 20.000, when compared to a direct DFT using real arithmetic. Hence one concludes \\(NORM>4000\\) to be sufficient for a negligible error \\((<0.05\\%)\\). No results of timing tests are included.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$4168B5C7-574A-4693-A2DE-9360DFC504CA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"588be99e69a86bc02ca9cc8ddd46725bc447e370","datavalue":{"value":"65T40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123580$6FBBC8DD-2274-4B1C-8D8B-00E11374C5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123580$A7F00A47-85CC-4870-B745-4B2767D0B65A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c922dcec2b90747b82a27659b55f3b66f3f134a9","datavalue":{"value":"4110059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123580$784FD380-179F-4E27-A539-E10C36C9DA7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"921833cfeadac16f6c8c9833e8e78cd4a5a6432d","datavalue":{"value":"fast algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$752FD2E7-47BE-493F-9FF7-81825C12A81E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1328eccdc9de6f1faba0b59107ec6c81584a0b77","datavalue":{"value":"fast Fourier transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$48E37251-D873-4553-A5F9-828AF662E95F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e078d1478828dcbc9815135559278a14d179e11","datavalue":{"value":"number theoretic transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$014F7C5C-C8FF-4E31-BE72-608CC09452D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"861e477912a2f75b76d4a0f9628e09b530824106","datavalue":{"value":"discrete Fourier transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$1964E180-C3D2-4B18-87C4-BF59CA3DD0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7e13171f0e301f9a7c03d8101ccbe541e557886","datavalue":{"value":"cyclic convolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$98DF3835-72B4-46F2-B7CE-97E4939C2605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849db0f9b181224c1cfc801586630a5ee7fec689","datavalue":{"value":"scaling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$D5CB6EF9-29BA-4845-B4FA-9C53C55D114B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26ef71165a72c40a713b975cce47d2d48f9f03ab","datavalue":{"value":"cyclic integer convolutions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$EC2E964E-0781-46A1-AA8A-D6D54C08BF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bf2159b83c1cb1978a8a55c136391b653478ee6","datavalue":{"value":"Chinese remainder theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123580$86C351FB-9946-4391-807B-6CD582C51A3D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ce5f65bda9473525ae76f6fddca6447d9c01ba3f","datavalue":{"value":{"entity-type":"item","numeric-id":1793929,"id":"Q1793929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$7EB48F8D-9A5F-4E01-9F7C-00AEF0F4B127","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$F1FB9625-0C91-419C-AB1D-947D50E5AA70","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"94b4dcc0c931e9140afb95e46dc96295204f1892","datavalue":{"value":"https://doi.org/10.1016/0016-0032(88)90031-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123580$310BB4BD-4BDA-4F3C-A6AB-512E763541A3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb941518c360c46f9dc686f7e1006a53998fd93b","datavalue":{"value":"W2063102759","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123580$095FA8F8-0540-494A-8423-05493F145BD7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd868ce1dbfc4d6f38bfad66c445685c537ca87b","datavalue":{"value":{"entity-type":"item","numeric-id":5332499,"id":"Q5332499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$5A459D7D-B888-439A-B1E8-5A8D822C34EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2433e31539d949ec90a0e3d7dc2383abd9720ee7","datavalue":{"value":{"entity-type":"item","numeric-id":5551900,"id":"Q5551900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$BC08C09B-0636-4A74-96BC-2C4F2A118620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0582a0a6fffe4ca8a1004571425ae9626fef4114","datavalue":{"value":{"entity-type":"item","numeric-id":4151723,"id":"Q4151723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$5F38C933-F6DA-4B6F-A416-7B85E06442DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7762601c52c6f56ad43c77280e69c30466acd787","datavalue":{"value":{"entity-type":"item","numeric-id":4107437,"id":"Q4107437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$80C18326-610E-44EC-9540-BD9CC9E6A46A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d2a688b22d3193cd86235ad5d8619da8efc626c","datavalue":{"value":{"entity-type":"item","numeric-id":3038577,"id":"Q3038577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$34CA3469-4D0D-4A0C-8135-A719EA3A7746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ee55b08c9654a83a9e47e25fd6a6fd9b04c62c4","datavalue":{"value":{"entity-type":"item","numeric-id":3036659,"id":"Q3036659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$04B91296-41DF-4EBF-B497-F40E50349466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e61ae052a45468c7fe8e7bee41be431cd8000d","datavalue":{"value":{"entity-type":"item","numeric-id":3698248,"id":"Q3698248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$882C24C5-1CA3-405E-9AC9-448F19C2DADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5864ff407691828143db89ed04abca180a61361","datavalue":{"value":{"entity-type":"item","numeric-id":2547695,"id":"Q2547695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$329F7CA0-3245-43A1-9B3E-C23614119086","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4babe5acd379f1156b6a418112f1afab4a8c795b","datavalue":{"value":{"entity-type":"item","numeric-id":5664781,"id":"Q5664781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$1E1E0981-577F-459D-ADF1-8D5C65692880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef8514aea9c04bd4771ca50f633fbaedcae5a5b6","datavalue":{"value":{"entity-type":"item","numeric-id":4054637,"id":"Q4054637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$80953337-3704-4A84-9D4E-9C00B6BD5455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d52bb7e7d554403b09aaeb785a51bee0f11f477b","datavalue":{"value":{"entity-type":"item","numeric-id":4088240,"id":"Q4088240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$E498C196-3CE7-4F58-BC95-AF460093F251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b51481658466fc5d8a631dd850493365fa10e02","datavalue":{"value":{"entity-type":"item","numeric-id":4156684,"id":"Q4156684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$CEE5D315-74B8-496D-A635-49A42BC119EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3340983737357d7aeb2ad2f6595d616b8b04e02d","datavalue":{"value":{"entity-type":"item","numeric-id":5534521,"id":"Q5534521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123580$9B5171C5-A106-433C-94F5-51468C6F92DA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f99e4046c0fade0020fad4b2dc1c5032f4341657","datavalue":{"value":{"entity-type":"item","numeric-id":3313766,"id":"Q3313766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b914c2f17d260346f9d279dff5e0592a4cd35588","datavalue":{"value":{"amount":"+0.8377488851547241","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123580$A304A864-2A26-4888-B9B5-EBFBA9B5F0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"372581834e998a1dd3478d6fdf3733767f0a5b21","datavalue":{"value":{"entity-type":"item","numeric-id":757003,"id":"Q757003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b77d2e72138f68878826ce52694f6be96648a28","datavalue":{"value":{"amount":"+0.8366557359695435","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123580$45455D7D-0806-491A-A304-031E3AB26C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced7ec53e612b02a302d6722ea68b898441b6774","datavalue":{"value":{"entity-type":"item","numeric-id":3691042,"id":"Q3691042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3413bcdb75915b5d39b427bc792a8c259830ec19","datavalue":{"value":{"amount":"+0.8146697282791138","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123580$1F406276-B512-438E-9CA5-197D510CFCD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecbb72ed4c49457d785fcb50d798d4b883e4738c","datavalue":{"value":{"entity-type":"item","numeric-id":3704820,"id":"Q3704820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6677d5cf7417badf7294fc137291878ea648cdc3","datavalue":{"value":{"amount":"+0.8130501508712769","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123580$C9660962-4C07-4824-B3A9-7A29223FB1D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c235d41e4d88d327b60e787685dcc9f81b235802","datavalue":{"value":{"entity-type":"item","numeric-id":3346383,"id":"Q3346383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40f2c9952175b5b23e8340b0857525267d7e52e9","datavalue":{"value":{"amount":"+0.8090500831604004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123580$99B1243B-617E-4E1F-B268-696C7B79C435","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fast Fourier transformation based on number theoretic transforms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fast_Fourier_transformation_based_on_number_theoretic_transforms"}}}}}