Questions tagged [integers]

Questions about properties of, working with and algorithms on integers.

Filter by
Sorted by
Tagged with
2
votes
1answer
537 views

4-partition elements summation NP completeness

How can we prove that the following problem $A$ is NP complete? Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \...
1
vote
1answer
81 views

How to determine the carry vector of an integer addition

An integer addition can be represented as following: $A + B = A \oplus B \oplus carry_{vector}$ My question is how to determine the carry vector from $A$ and $B$ (not from the result)?
2
votes
1answer
149 views

How to uniquely encode a vector of non-increasing positive integers

Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the ...
5
votes
0answers
86 views

What are applications to sort plain integer arrays?

A lot of research and engineering effort is put into finding fast methods to sort an array of integers; e.g., Java's runtime library has highly-tuned methods to sort arrays of each primitive type (see ...
3
votes
1answer
5k views

Complexity of Integer Division

My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem: 1-28. [5] Write a function to perform integer division without using either the / or * ...
1
vote
1answer
596 views

There are n numbers. Find the maximal set of pairwise NON coprime numbers

I have to take input in an array(no. of elements in array <=10^5). For ex:- Let the array be {2,3,4,16,9,45,81,27} Now I need to find the order of the maximal set such that any pair of elements in ...
1
vote
1answer
259 views

Complexity class of integer factorization

Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is ...
2
votes
2answers
669 views

Find the duplicates in a list of floating point numbers

I receive a list of real numbers ( float ) between $0$ and $1$. The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ ...
2
votes
2answers
118 views

Problems that become far easier when restricted to only integer values

I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values. One such example would be sorting ...
2
votes
2answers
186 views

Efficient algorithm for getting from 1 to n with 3 specific operations

The question: Given those 3 valid operations over numbers and an integer $n$: add $1$ to the number multiply the number by $2$ multiply the number by $3$ describe an efficient ...
2
votes
0answers
53 views

Are there any practical drop-in replacements for BSTs in the case where data are integers?

There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement ...
1
vote
3answers
5k views

Sum of 3 integers with full adder

1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image ...
2
votes
1answer
936 views

Convert integer of mixed radix to standard positional numeral system and vice versa

I have multiple numbers (e.g. [1, 4, 2]) where each number can be one of a specified range of numbers (e.g. [0-1, 0-5, 0-3]). I ...
3
votes
0answers
25 views

Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root

tl;dr? See last paragraph. If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form $ x_{k+1} = \frac{x_k\Big[A\...
3
votes
1answer
418 views

Optimal quantization of histogram

I have a histogram of occurrences, as a list of counts (non-negative integers). For the purposes of a compression algorithm (specifically arithmetic coding) I must quantize these occurrences into a ...
4
votes
1answer
29 views

Compactly representing integers when allowed a multiplicative error

Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$. Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits. In contrast, assume we are ...
3
votes
1answer
383 views

Where can I find an original reference for this integer square root algorithm

As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary. I'm sure this is not original; can anyone provide a reference? ...
1
vote
1answer
131 views

Sum to a certain value of a group of integers

Take a group filled with an arbitrary number of random integers. Is there any way of finding out whether it is possible for the sum of the integers can equal a certain number, with the condition that ...
3
votes
2answers
108 views

Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?

Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ ...
2
votes
4answers
701 views

Counting an integer's divisors without just enumerating them (or estimating if not possible)?

I'm trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$. For ...
5
votes
1answer
186 views

Practical Implementation for Refinement Order on Integer Partitions

The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ ...
22
votes
3answers
1k views

Algorithm to minimize surface area, given volume

Consider the following algorithmic task: Input: a positive integer $n$, along with its prime factorization Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $...
4
votes
2answers
516 views

Are nearly all natural numbers compressible?

A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov ...
24
votes
2answers
729 views

Efficient algorithm for 'unsumming' a set of sums

Given a multiset of natural numbers X, consider the set of all possible sums: $$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$ For example, $\textrm{sums}(\left\{1,5\right\...
3
votes
1answer
53 views

"Most Similar Vector Problem" on an Integer Lattice

I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum. Given $u \in \mathbb{R}^n$ and a bounded integer ...
1
vote
1answer
31 views

Complexity of finding these original parameters

I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple ...
5
votes
3answers
369 views

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

I'm currently reading the elements of programming book and have come across a section I don't quite understand A computational basis for a type is a finite set of procedures that enable the ...
5
votes
2answers
1k views

Find 8 numbers whose sum is closest to a defined value

I have a file that has a number (a positive integer) on each row. Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible. So, ...
9
votes
1answer
2k views

Algorithm for multiplying multivariate polynomials

Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$. How fast can we compute the product of $f$ ...
6
votes
3answers
286 views

Find the minimum range

Given a list of numbers as L, how do you find the minimum value m such that L can be made ...
7
votes
3answers
479 views

Unreachable Real Numbers - Randomness & Computability

I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...
0
votes
1answer
67 views

Integer factorization: comparing with floor

While working on integer factorization algorithm I came to the next problem: $$\frac{a}{ex} = \lfloor{\frac{a}{ex}\rfloor} + c$$ $a$ the number I want to factor $x$ factor of $a$ $e$ positive ...
0
votes
1answer
89 views

Rounding errors when converting floats to integers

Is it possible to have a rounding error when you convert a floating point number which can only be in increments of 0.01 to an integer by multiplying by 100 first? I would think that the lack of ...
1
vote
2answers
373 views

What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well. I also know that is it somewhat ...
2
votes
0answers
527 views

Quick method for approximate integer square roots

I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties: $(\bar{n}+1)^2>n$; $(\bar{n}-1)^2<n$; So we have $\...
0
votes
1answer
50 views

Use of -1 to express edge cases in computer programs and data structures [closed]

Often I will encounter the use of - or even use myself - the value -1 as an edge case in otherwise integer data structures. For instance, as the value for "...
4
votes
2answers
1k views

How are Signed integers different from unsigned integers once compiled

How are Signed integers different from unsigned integers once compiled? I already know about twos compliment and the like but my question is how can you tell the difference when looking at 8 bit ...
1
vote
1answer
133 views

How many ways to find a sum totalling n using only certain Integers?

Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n? Clarification: The Integers are arbitrary, positive, and may not include 1. At first I thought it was ...
6
votes
1answer
739 views

Complexity of Linear Diophantine equations

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...
5
votes
1answer
486 views

Difference in Sorting 32- and 64-bit Integers

In 2007, Barrack Obama was interviewed at Google. The question was, "What is the best way to sort a million 32-bit integers?" Does the fact that the size range of the integer was specified elude to a ...
0
votes
1answer
186 views

How to store factorials? [closed]

Can someone help me to store the factorial of large numbers such as 100! efficiently? UPDATE: obviously, storing the argument rather than the factorial digits themselves achieves a significant saving....
2
votes
1answer
80 views

Checking whether a number is a square or higher power modulo n

Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know? Is the Jacobi symbol helpful? What about higher powers, e.g.,...
5
votes
1answer
133 views

Checking whether an integer is a square or higher power

Is there an algorithm to check whether an integer $n$ is a square? What about higher powers, e.g., testing whether $n$ is a $k$th power? I understand that the Jacobi symbol $\left(\frac{b}{n}\right)$...
9
votes
1answer
436 views

What algorithms exist for solving natural number linear systems?

I'm looking at the following problem: Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number ...
7
votes
2answers
442 views

Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ...
1
vote
1answer
135 views

Algorithm to decide if $n \le m!$

This is an assignment of an introductory course of complexity theory and I need to find a way to do the following: Given $n,m \in \Bbb N$, is $n \le m!$ ? The idea is to provide a Post Machine that ...
5
votes
2answers
104 views

Quick calculation for $(x^y) \bmod z$

What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers? Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.
2
votes
3answers
1k views

Computing a histogram with the number of extant values not known in advance

(This may be more fitting for CSTheory, I'm not sure.) I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for ...
3
votes
1answer
569 views

Shift-and-or multiplication operation

Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold): Let $r = p \oplus q$ be an operation similar to multiplication, but ...
3
votes
2answers
1k views

Carry-free multiplication operation

In long-multiplication, you shift and add, once for each $1$ bit in the lower number. Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-...