<p>I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are sparse and have a periodic pattern but have different periodic pattern. How should I modify the Fourier Transform technique? Would a downsampling and upsampling technique based transform technique help?</p>

<p>Let $A$ and $B$ be $n^{3}M$ bit positive integers with special structure. </p>

<p><strong>Structure of A</strong></p>

<p>The first $nM$ bits have information and the next $(n^{2}-n)M$ bits are $0$. The next $nM$ bits have information followed by $(n^{2}-n)M$ bits of $0$. The structure repeats.</p>

<p><strong>Structure of B</strong></p>

<p>The first $M$ bits have information and the next $(n-1)M$ bits are $0$. The next $M$ bits have information followed by $(n-1)M$ bits of $0$. The structure repeats.</p>

<p>Let $p$ be an $n^{2}M$ bit prime number or power of prime.</p>

<p>Can I compute $AB \mbox{ mod } p$ with $O(n^{2}M)$ extra space (by this I mean only $A$, $B$ requires $O(n^{3}M)$ space to store and every thing else needs to be done in place with only $O(n^{2}M)$ space) and in $O(n^{2}M^{1}\log^{2}({n^{2}M^{1}}))$ time? This seems very likely as since $A$ and $B$ are sparse and have only $O(n^{2}M)$ bits of information.</p>

<p>(One can assume $M=1$ for simplicity $w.l.o.g$).</p>

<p>Refer <a href="https://mathoverflow.net/questions/43268/integer-multiplication-question">https://mathoverflow.net/questions/43268/integer-multiplication-question</a> for a variant and polynomial set up to the related problem</p>

CC BY-SA 2.5
2010-10-23T13:17:02.593Z
You are doing it again.  Please learn that it is [discouraged to crosspost simultaneously](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).  http://mathoverflow.net/questions/43268/integer-multiplication-question
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-23T17:03:20.080Z
tsuyoshi.. the questions were supposed to be different
Turbo
CC BY-SA 2.5
2010-10-24T03:40:57.867Z
(Reposting a comment with a minor edit because my previous comment disappeared during the [datacenter relocation](http://blog.serverfault.com/post/1383845452/datacenter-move-engage).)  The two questions were identical letter-to-letter when I posted my previous comment.  You changed the question on MathOverflow a few hours after I posted my comments to both pages.  As I understand it, you are posting these questions at two different places trying to get attention of more people than the questions deserve.  I understand that you are desperate, but that does not justify your action.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-24T05:08:44.970Z
Well Tsuyoshi.. how do you know what problems a person has in mind before shooting a question here? How can you judge whether a question desrves attention or not? If you look at the questions carefully there are subtle differences in the final answer. (The first question was the same). Also it would be good to get a mathematicians view point as well a complexity theorists view point.
Turbo
CC BY-SA 2.5
2010-10-24T08:14:29.183Z
@user1812: In any case, you should be honest and disclose that you have crossposted the question, and on both sites give links to the question on the other site. Then people who try to answer your question can also benefit from the discussion on the other site.
Jukka Suomela
CC BY-SA 2.5
2010-10-24T08:18:22.763Z
@Jukka I see your point
Turbo
<ds.algorithms><algebraic-complexity><linear-algebra>
Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound
Turbo
# Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound

(Asked by: username_0 on 2010-10-23)

I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are sparse and have a periodic pattern but have different periodic pattern. How should I modify the Fourier Transform technique? Would a downsampling and upsampling technique based transform technique help?

Let $A$ and $B$ be $n^{3}M$ bit positive integers with special structure.

**Structure of A**

The first $nM$ bits have information and the next $(n^{2}-n)M$ bits are $0$. The next $nM$ bits have information followed by $(n^{2}-n)M$ bits of $0$. The structure repeats.

**Structure of B**

The first $M$ bits have information and the next $(n-1)M$ bits are $0$. The next $M$ bits have information followed by $(n-1)M$ bits of $0$. The structure repeats.

Let $p$ be an $n^{2}M$ bit prime number or power of prime.

Can I compute $AB \mbox{ mod } p$ with $O(n^{2}M)$ extra space (by this I mean only $A$, $B$ requires $O(n^{3}M)$ space to store and every thing else needs to be done in place with only $O(n^{2}M)$ space) and in $O(n^{2}M^{1}\log^{2}({n^{2}M^{1}}))$ time? This seems very likely as since $A$ and $B$ are sparse and have only $O(n^{2}M)$ bits of information.

(One can assume $M=1$ for simplicity $w.l.o.g$).

Refer <https://mathoverflow.net/questions/43268/integer-multiplication-question> for a variant and polynomial set up to the related problem

**Tags:** ds.algorithms, algebraic-complexity, linear-algebra

> **Comments:**
> **username_1**: You are doing it again.  Please learn that it is [discouraged to crosspost simultaneously](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).  http://mathoverflow.net/questions/43268/integer-multiplication-question  
> **username_0**: tsuyoshi.. the questions were supposed to be different  
> **username_1**: (Reposting a comment with a minor edit because my previous comment disappeared during the [datacenter relocation](http://blog.serverfault.com/post/1383845452/datacenter-move-engage).)  The two questions were identical letter-to-letter when I posted my previous comment.  You changed the question on MathOverflow a few hours after I posted my comments to both pages.  As I understand it, you are posting these questions at two different places trying to get attention of more people than the questions deserve.  I understand that you are desperate, but that does not justify your action.  
> **username_0**: Well Tsuyoshi.. how do you know what problems a person has in mind before shooting a question here? How can you judge whether a question desrves attention or not? If you look at the questions carefully there are subtle differences in the final answer. (The first question was the same). Also it would be good to get a mathematicians view point as well a complexity theorists view point.  
> **username_2**: @user1812: In any case, you should be honest and disclose that you have crossposted the question, and on both sites give links to the question on the other site. Then people who try to answer your question can also benefit from the discussion on the other site.  
> **username_0**: @Jukka I see your point  

---

## 0 answers

