# Questions tagged [integers]

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

114 questions
Filter by
Sorted by
Tagged with
688 views

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 "...
678 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 ...
128 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 ...
406 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 ...
425 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 ...
147 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....
73 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.,...
119 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)$...
364 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 ...
289 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 ...
133 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 ...
97 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$.
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 ...
551 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 ...
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-...
500 views

### Best complexity of parity/comparison in the Residue Number System

Let: $\left\{m_1, ~...~, m_k\right\}$ be a set of coprime natural numbers, $M=\prod_{i=1}^{k} m_i$ $X$ be a natural integer, such that $X < M$ Then $X$ can be expressed in the Residue Number ...
280 views

### Division by a constant

After skimming Multiplication by a Constant is Sublinear (PDF), (slides (PDF), slides with notes (PDF)) I was wondering if this could be extended to division by a constant in sublinear time? ...
159 views

### Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator

C++11 has a convenient Bernoulli RNG, illustrated at http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution . However, distilling an entire random integer into a single random bit ...
4k views

### What data structure would efficiently store integer ranges?

I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following: Insert a new integer Insert a range of contiguous integers Remove an integer Remove all ...
1k views

### Filling Rows of a Matrix Subject to Conditions

I'm seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)(N+2)(N+3)/6 rows and 4 columns with the integers from 0, ... , N, subject to the conditions that: ...
336 views

### Number of multisets such that each number from 1 to $n$ can be uniquely expressed as a sum of some of the elements of the multiset

My problem. Given $n$, I want to count the number of valid multisets $S$. A multiset $S$ is valid if The sum of the elements of $S$ is $n$, and Every number from $1$ to $n$ can be expressed uniquely ...
105 views

### Remove divisors from a set of integers

I have a set $S$ of integers. I want to remove all elements of $S$ that are divisors of another element of $S$. In other words, I want to compute $T = \{y \in S : \forall d \in S . d \nmid y \}$. ...
2k views

### Algorithm to determine if a number is perfect on a Turing Machine

I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it ...
6k views

### What are two's complement integers?

Can someone explain in plain English what "two's complement integer" means? I read this: in Java long is a 64-bit signed two's complement integer
25 views

### VAR autoincrement with constant space consumption for super large tables

Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs ...
6k views

### Algorithm to return largest subset of non-intersecting intervals

I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals. i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ ...