Document Open Access Logo

Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements

Authors Mitsuru Funakoshi , Julian Pape-Lange

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.30.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Mitsuru Funakoshi
  • Department of Informatics, Kyushu University, Japan
Julian Pape-Lange
  • Technische Universität Chemnitz, Straße der Nationen 62, 09111 Chemnitz, Germany

Acknowledgements

The first author discovered an error in the algorithm for determining the existence of 3-cadences in "String cadences" of Amir et al., which led to false positives. After that, the first author reported this error to Travis Gagie, one of the authors of "String Cadences". Travis Gagie explained this error to the second author during the 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) in Pisa. He also claimed that it should be possible to determine the existence of 3-cadences in sub-quadratic time. Juliusz Straszyński showed during the same conference that 3-sub-cadences beginning and ending in given intervals can efficiently be detected by convolution. Amihood Amir noted later in an email that we can also efficiently count these sub-cadences, which allows "subtractive" methods as used for arbitrary triangles.

Cite AsGet BibTex

Mitsuru Funakoshi and Julian Pape-Lange. Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.30

Abstract

The discrete acyclic convolution computes the 2n+1 sums ∑_{i+j=k|(i,j)∈[0,1,2,… ,n]²} a_i b_j in ?(n log n) time. By using suitable offsets and setting some of the variables to zero, this method provides a tool to calculate all non-zero sums ∑_{i+j=k|(i,j)∈ P∩ℤ²} a_i b_j in a rectangle P with perimeter p in ?(p log p) time. This paper extends this geometric interpretation in order to allow arbitrary convex polygons P with k vertices and perimeter p. Also, this extended algorithm only needs ?(k + p(log p)² log k) time. Additionally, this paper presents fast algorithms for counting sub-cadences and cadences with 3 elements using this extended method.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Combinatorics on words
  • Theory of computation → Computational geometry
  • Computing methodologies → Number theory algorithms
Keywords
  • discrete acyclic convolutions
  • string-cadences
  • geometric algorithms
  • number theoretic transforms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. R. C. Agarwal and C. S. Burrus. Number theoretic transforms to implement fast digital convolution. Proceedings of the IEEE, 63(4):550-560, April 1975. URL: https://doi.org/10.1109/PROC.1975.9791.
  2. Amihood Amir, Alberto Apostolico, Travis Gagie, and Gad M. Landau. String cadences. Theoretical Computer Science, 698:4-8, 2017. Algorithms, Strings and Theoretical Approaches in the Big Data Era (In Honor of the 60th Birthday of Professor Raffaele Giancarlo). URL: https://doi.org/10.1016/j.tcs.2017.04.019.
  3. N. C. Ankeny. The Least Quadratic Non Residue. Annals of Mathematics, 55(1):65-72, 1952. URL: http://www.jstor.org/stable/1969420.
  4. Eric Bach and Jonathan Sorenson. Explicit bounds for primes in residue classes. Math. Comput., 65(216):1717-1735, October 1996. URL: https://doi.org/10.1090/S0025-5718-96-00763-6.
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  6. Svyatoslav Covanov and Emmanuel Thomé. Fast integer multiplication using generalized fermat primes. Math. Comp., 88(317):1449-1477, 2019. URL: https://doi.org/10.1090/mcom/3367.
  7. Anindya. De, Piyush P. Kurur, Chandan. Saha, and Ramprasad. Saptharishi. Fast integer multiplication using modular arithmetic. SIAM Journal on Computing, 42(2):685-699, 2013. URL: https://doi.org/10.1137/100811167.
  8. J. Gardelle. Cadences. Mathématiques et Sciences humaines, 9:31-38, 1964. URL: http://www.numdam.org/item/MSH_1964__9__31_0.
  9. D. Harvey and J. van der Hoeven. Faster integer multiplication using plain vanilla FFT primes. Math. Comp., 88(315):501-514, 2019. Google Scholar
  10. D. Harvey and J. van der Hoeven. Integer multiplication in time O(n log n). working paper or preprint, March 2019. URL: https://hal.archives-ouvertes.fr/hal-02070778.
  11. D. Harvey, J. van der Hoeven, and G. Lecerf. Even faster integer multiplication. Journal of Complexity, 36:1-30, 2016. URL: https://doi.org/10.1016/j.jco.2016.03.001.
  12. D. R. Heath-Brown. Almost-primes in arithmetic progressions and short intervals. Mathematical Proceedings of the Cambridge Philosophical Society, 83(3):357–375, 1978. URL: https://doi.org/10.1017/S0305004100054657.
  13. Christos Levcopoulos and Andrzej Lingas. Bounds on the length of convex partitions of polygons. In Mathai Joseph and Rudrapatna Shyamasundar, editors, Foundations of Software Technology and Theoretical Computer Science, pages 279-295, Berlin, Heidelberg, 1984. Springer Berlin Heidelberg. Google Scholar
  14. U. V. Linnik. On the least prime in an arithmetic progression. I. The basic theorem. Rec. Math. [Mat. Sbornik] N.S., 15(57):139-178, 1944. Google Scholar
  15. M. Lothaire. Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press, 1997. URL: https://books.google.de/books?id=eATLTZzwW-sC.
  16. Franz Mertens. Ein Beitrag zur analytischen Zahlentheorie. Journal für die reine und angewandte Mathematik, 78:46-62, 1874. URL: http://eudml.org/doc/148244.
  17. A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7(3):281-292, September 1971. URL: https://doi.org/10.1007/BF02242355.
  18. William B. Thompson, Peter Shirley, and James A. Ferwerda. A Spatial Post-Processing Algorithm for Images of Night Scenes. Journal of Graphics Tools, 7(1):1-12, 2002. URL: https://doi.org/10.1080/10867651.2002.10487550.
  19. Bartel Leendert van der Waerden. Beweis einer Baudet’schen Vermutung. Nieuw Archief voor Wiskunde, 15:212-216, 1927. Google Scholar
  20. Samuel S. Wagstaff. Greatest of the least primes in arithmetic progressions having a given modulus. Mathematics of Computation, 33(147):1073-1080, 1979. URL: http://www.jstor.org/stable/2006082.
  21. Triantafyllos Xylouris. Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, volume 404 of Bonner Mathematische Schriften [Bonn Mathematical Publications]. Universität Bonn, Mathematisches Institut, Bonn, 2011. Dissertation for the degree of Doctor of Mathematics and Natural Sciences at the University of Bonn, Bonn, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact