Выражение целого числа как ряда множителей

Ответ 1

Обновление

Я не мог удержаться от попыток придумать собственное решение для первого вопроса, даже если он не выполняет сжатие. Вот решение Python, использующее алгоритм факторизации третьей стороны, называемый pyecm.

Это решение, вероятно, на несколько величин более эффективно, чем у Евгения. Вычисления занимают секунды вместо часов или, возможно, даже недель/лет для разумных значений y. Для x = 2 ^ 32-1 и y = 256 на мой основной дуэт 1,2 ГГц потребовалось 1,68 секунды.

>>> import time
>>> def test():
...     before = time.time()
...     print factor(2**32-1, 256)
...     print time.time()-before
...
>>> test()
[254, 232, 215, 113, 3, 15]
1.68499994278
>>> 254*232*215*113*3+15
4294967295L

И вот код:

def factor(x, y):
    # y should be smaller than x. If x=y then {y, 1, 0} is the best solution
    assert(x > y)

    best_output = []

    # try all possible remainders from 0 to y 
    for remainder in xrange(y+1):
        output = []
        composite = x - remainder
        factors = getFactors(composite)

        # check if any factor is larger than y
        bad_remainder = False
        for n in factors.iterkeys():
            if n > y: 
                bad_remainder = True
                break
        if bad_remainder: continue

        # make the best factors
        while True:
            results = largestFactors(factors, y)
            if results == None: break
            output += [results[0]]
            factors = results[1]

        # store the best output
        output = output + [remainder]
        if len(best_output) == 0 or len(output) < len(best_output):
            best_output = output

    return best_output

# Heuristic
# The bigger the number the better. 8 is more compact than 2,2,2 etc...

# Find the most factors you can have below or equal to y
# output the number and unused factors that can be reinserted in this function
def largestFactors(factors, y):
    assert(y > 1)
    # iterate from y to 2 and see if the factors are present.
    for i in xrange(y, 1, -1):
        try_another_number = False
        factors_below_y = getFactors(i)
        for number, copies in factors_below_y.iteritems():
            if number in factors:
                if factors[number] < copies:
                    try_another_number = True
                    continue # not enough factors
            else:
                try_another_number = True
                continue # a factor is not present

        # Do we want to try another number, or was a solution found?
        if try_another_number == True:
            continue
        else:
            output = 1
            for number, copies in factors_below_y.items():
                remaining = factors[number] - copies
                if remaining > 0:
                    factors[number] = remaining
                else:
                    del factors[number]
                output *= number ** copies

            return (output, factors)

    return None # failed




# Find prime factors. You can use any formula you want for this.
# I am using elliptic curve factorization from http://sourceforge.net/projects/pyecm
import pyecm, collections, copy

getFactors_cache = {}
def getFactors(n):
    assert(n != 0)
    # attempt to retrieve from cache. Returns a copy
    try:
        return copy.copy(getFactors_cache[n])
    except KeyError:
        pass

    output = collections.defaultdict(int)
    for factor in pyecm.factors(n, False, True, 10, 1):
        output[factor] += 1

    # cache result
    getFactors_cache[n] = output

    return copy.copy(output)

Ответ на первый вопрос

Вы говорите, что хотите сжатие чисел, но из ваших примеров эти последовательности длиннее нераспределенных чисел. Невозможно сжать эти числа без дополнительной информации в систему, которую вы оставили (вероятность последовательности/есть программируемый клиент?). Не могли бы вы подробнее рассказать?

Вот математическое объяснение того, почему текущие ответы на первую часть вашей проблемы никогда не решат вашу вторую проблему. Это не имеет никакого отношения к проблеме ранца.

Это алгоритм энтропии Шеннона. Он сообщает вам теоретическое минимальное количество бит, которое вам нужно представлять последовательность {X0, X1, X2,..., Xn-1, Xn}, где p (Xi) - вероятность видеть токен Xi.

Скажем, что X0-Xn - это диапазон от 0 до 4294967295 (диапазон целого числа). Из того, что вы описали, каждый номер так же вероятен, как и другой. Поэтому вероятность каждого элемента равна 1/4294967296.

Когда мы подключаем его к алгоритму Шеннона, он скажет нам, какое минимальное количество бит необходимо для представления потока.

import math

def entropy():
    num = 2**32
    probability = 1./num
    return -(num) * probability * math.log(probability, 2)
    # the (num) * probability cancels out

Энтропия неудивительно - 32. Нам нужно 32 бита для представления целого числа, где каждое число одинаково вероятно. Единственный способ уменьшить это число - увеличить вероятность некоторых чисел и уменьшить вероятность других. Вы должны объяснить поток более подробно.

Ответ на второй вопрос

Правильный способ сделать это - использовать base64 при общении с HTTP. По-видимому, Java не имеет этого в стандартной библиотеке, но я нашел ссылку на бесплатную реализацию:

http://iharder.sourceforge.net/current/java/base64/

Вот "псевдокод", который отлично работает на Python и не должен быть сложно преобразовать в Java (моя Java ржавая):

def longTo64(num):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"
    output = ""

    # special case for 0
    if num == 0:
        return mapping[0]

    while num != 0:
        output = mapping[num % 64] + output
        num /= 64

    return output

Если вы контролируете свой веб-сервер и веб-клиент и можете без проблем обрабатывать все HTTP-запросы, вы можете перейти на base85. Согласно wikipedia, кодировка url допускает до 85 символов. В противном случае вам может потребоваться удалить несколько символов из сопоставления.

Вот еще один пример кода в Python

def longTo85(num):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~!*'();:@&=+$,/?%#[]"
    output = ""
    base = len(mapping)

    # special case for 0
    if num == 0:
        return mapping[0]

    while num != 0:
        output = mapping[num % base] + output
        num /= base

    return output

И вот обратная операция:

def stringToLong(string):
    mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_.~!*'();:@&=+$,/?%#[]"
    output = 0
    base = len(mapping)

    place = 0
    # check each digit from the lowest place
    for digit in reversed(string):
        # find the number the mapping of symbol to number, then multiply by base^place
        output += mapping.find(digit) * (base ** place)
        place += 1

    return output

Вот график алгоритма Шеннона в разных базах.

Как вы можете видеть, чем выше радикс, тем меньше символов необходимо для представления числа. В base64 требуется ~ 11 символов для представления long. В базе85 оно становится ~ 10 символами.

Ответ 2

Изменить после окончательного объяснения:

Я бы подумал, что base64 - лучшее решение, так как есть стандартные функции, которые с ним справляются, а варианты этой идеи не дают большого улучшения. Об этом ответили гораздо более подробно другие.

Относительно исходного вопроса, хотя код работает, он не может быть запущен в любое разумное время, как было ответили, а также прокомментировал этот вопрос LFSR Consulting.

Исходный ответ:

Вы имеете в виду что-то вроде этого?

Изменить - исправлено после комментария.

shortest_output = {}

foreach (int R = 0; R <= X; R++) {
    // iteration over possible remainders
    // check if the rest of X can be decomposed into multipliers
    newX = X - R;
    output = {};

    while (newX > Y) {
       int i;
       for (i = Y; i > 1; i--) {
           if ( newX  % i == 0) { // found a divider
           output.append(i);
           newX  = newX /i;  
           break;
           }
       }

       if (i == 1) { // no dividers <= Y
          break;
       }
    }
    if (newX != 1) {
        // couldn't find dividers with no remainder
        output.clear();
    }
    else {
        output.append(R);
            if (output.length() < shortest_output.length()) {
                 shortest_output = output;
            }
    }
}

Ответ 3

Звучит так, как будто вы хотите сжать случайные данные - это невозможно по теоретико-информационным причинам. (См. http://www.faqs.org/faqs/compression-faq/part1/preamble.html вопрос 9.) Используйте Base64 для конкатенированных двоичных представлений ваших номеров и сделайте с ним.

Ответ 4

Проблема, которую вы пытаетесь решить (вы имеете дело с подмножеством проблемы, если вы ограничены y), называется Целочисленная факторизация, и это невозможно сделать эффективно с помощью любого известного алгоритма:

В теории чисел целочисленная факторизация представляет собой разбиение составного числа на более мелкие нетривиальные делители, которые при умножении вместе равны исходному целу.

Эта проблема заключается в том, что делает возможным ряд криптографических функций (а именно RSA, который использует 128-битные ключи) - это половина этого.) Страница вики содержит некоторые хорошие ресурсы, которые должны перемещать вас в правильном направлении с вашей проблемой.

Итак, ваш мозговой тизер действительно мозговой тизер... и если вы решите его эффективно, мы сможем повысить ваши математические навыки до уровня выше среднего.

Ответ 5

Обновлено после полной истории

Base64, скорее всего, ваш лучший вариант. Если вы хотите создать собственное решение, вы можете попробовать внедрить систему Base 65+. Просто помните, что только потому, что 10000 можно записать как "10 ^ 4", это не означает, что все можно записать в виде 10 ^ n, где n - целое число. Различные базовые системы - это самый простой способ записи чисел, и чем выше база, тем меньше цифр требуется число. Кроме того, большинство библиотечных библиотек содержат алгоритмы кодирования Base64. (Какой язык вы используете?).

Один из способов дальнейшего размещения URL-адресов - это тот, который вы упомянули, но в Base64.

int[] IDs;
IDs.sort() // So IDs[i] is always smaller or equal to IDs[i-1].

string url = Base64Encode(IDs[0]);

for (int i = 1; i < IDs.length; i++) {
  url += "," + Base64Encode(IDs[i-1] - IDs[i]);
}

Обратите внимание, что вам нужен некоторый разделитель, поскольку начальный идентификатор может быть сколь угодно большим, а разница между двумя идентификаторами МОЖЕТ быть больше 63, и в этом случае недостаточно одной цифры Base64.

Обновление

Просто повторю, что проблема неразрешима. Для Y = 64 вы не можете написать 87681 в множителях + остаток, где каждый из них ниже 64. Другими словами, вы не можете написать ни одного из чисел 87617..87681 с множителями, которые ниже 64. Каждое из этих чисел имеет элементарный член более 64. 87616 можно записать в элементарных терминах ниже 64, но тогда вам понадобится их + 65, и поэтому остаток будет больше 64.

Итак, если это был просто бреток, это невозможно. Была ли какая-то практическая цель для этого, которая могла быть достигнута каким-то образом, кроме использования умножения и остатка?

И да, это действительно должен быть комментарий, но я потерял способность комментировать в какой-то момент.: Р

Я считаю, что решение, которое ближе всего подходит, - это Евгений. Также легко расширить решение Евгения, чтобы удалить предел для остатка, и в этом случае он сможет найти решение, где множители меньше Y и остатка как можно меньше, даже если оно больше Y.

Старый ответ:

Если вы ограничиваете, что каждое число в массиве должно быть ниже y, тогда для этого нет решения. При достаточно большом x и достаточно малом y вы окажетесь в невозможной ситуации. В качестве примера с y из 2, x из 12 вы получите 2 * 2 * 2 + 4, так как 2 * 2 * 2 * 2 будет 16. Даже если вы разрешите отрицательные числа с абс (n) ниже y, t, так как вам понадобится 2 * 2 * 2 * 2 - 4 в приведенном выше примере.

И я думаю, что проблема NP-Complete, даже если вы ограничиваете проблему входами, которые, как известно, имеют ответ, где последний член меньше y. Это очень похоже на проблему [Knapsack] [1]. Конечно, я ошибаюсь.

Edit:

Без более точного описания проблемы трудно решить проблему, но один вариант может работать следующим образом:

• set current = x
• Прерывать ток до его терминов
• Если одно из термов больше y, то текущее число не может быть описано в терминах, больших y. Уменьшите один из текущего и повторите с 2.
• Текущее число может быть выражено в единицах меньше y.
• Рассчитать остаток
• Объедините как можно больше терминов.

(У Евгения Доктора есть более цельная (и работающая) реализация этого, чтобы предотвратить путаницу, я пропустил реализацию.)

Ответ 6

ОП писал:

Моя цель состояла в том, чтобы придумать конкретный метод для упаковки 1..n большой целые числа (aka longs) вместе, так что их строковое представление заметно короче, чем написание фактических номер. Подумайте, кратные десяти, 10 ^ 6 и 1 000 000 одинаковы, однако длина представления в символов нет.

Я раньше был на этом пути, и, как весело, чтобы изучать всю математику, чтобы сэкономить ваше время, я просто укажу вам на: http://en.wikipedia.org/wiki/Kolmogorov_complexity

В двух словах некоторые строки можно легко сжать, изменив ваши обозначения:

10^9 (4 characters) = 1000000000 (10 characters)

Другие не могут:

7829203478 = some random number...

Это отличное упрощение статьи, связанной с выше, поэтому я рекомендую вам прочитать ее, а не принимать мои объяснения по номинальной стоимости.

Edit: Если вы пытаетесь сделать URL RESTful для некоторого набора уникальных данных, почему бы вам не использовать хэш, например MD5? Затем включите хэш как часть URL-адреса, затем найдите данные на основе хеша. Или я пропущу что-то очевидное?

Ответ 7

Обновление: Я не получил все, поэтому я переписал все это в стиле Java-Style. Я не думал о простом номере, который больше, чем делитель. Теперь это исправлено. Я оставляю исходный код, чтобы получить эту идею.

Обновление 2: Теперь я обрабатываю случай большого простого числа другим способом. Таким образом, результат получается в любом случае.

public final class PrimeNumberException extends Exception {

    private final long primeNumber;

    public PrimeNumberException(long x) {
        primeNumber = x;
    }

    public long getPrimeNumber() {
        return primeNumber;
    }
}

public static Long[] decompose(long x, long y) {
    try {
        final ArrayList<Long> operands = new ArrayList<Long>(1000);
        final long rest = x % y;
        // Extract the rest so the reminder is divisible by y
        final long newX = x - rest;
        // Go into recursion, actually it a tail recursion
        recDivide(newX, y, operands);            
    } catch (PrimeNumberException e) {
        // return new Long[0];
        // or do whatever you like, for example
        operands.add(e.getPrimeNumber());
    } finally {
        // Add the reminder to the array
        operands.add(rest);
        return operands.toArray(new Long[operands.size()]);
    }
}

// The recursive method
private static void recDivide(long x, long y, ArrayList<Long> operands)
    throws PrimeNumberException {
    while ((x > y) && (y != 1)) {
        if (x % y == 0) {
            final long rest = x / y;
            // Since y is a divisor add it to the list of operands
            operands.add(y);
            if (rest <= y) {
                // the rest is smaller than y, we're finished
                operands.add(rest);
            }
            // go in recursion
            x = rest;
        } else {
            // if the value x isn't divisible by y decrement y so you'll find a 
            // divisor eventually
            if (--y == 1) {
                throw new PrimeNumberException(x);
            }
        }
    }
}

Оригинал: Вот какой рекурсивный код я придумал. Я бы предпочел кодировать его на каком-то функциональном языке, но это требовалось на Java. Я не удосужился преобразовать числа в целое, но это не должно быть так сложно (да, я ленив;)

public static Long[] decompose(long x, long y) {
    final ArrayList<Long> operands = new ArrayList<Long>();
    final long rest = x % y;
    // Extract the rest so the reminder is divisible by y
    final long newX = x - rest;
    // Go into recursion, actually it a tail recursion
    recDivide(newX, y, operands);
    // Add the reminder to the array
    operands.add(rest);
    return operands.toArray(new Long[operands.size()]);
}

// The recursive method
private static void recDivide(long newX, long y, ArrayList<Long> operands) {
    long x = newX;
    if (x % y == 0) {
        final long rest = x / y;
        // Since y is a divisor add it to the list of operands
        operands.add(y);
        if (rest <= y) {
            // the rest is smaller than y, we're finished
            operands.add(rest);
        } else {
            // the rest can still be divided, go one level deeper in recursion
            recDivide(rest, y, operands);
        }
    } else {
        // if the value x isn't divisible by y decrement y so you'll find a divisor    
        // eventually
        recDivide(x, y-1, operands);
    }
}

Ответ 8

Исходным методом, который вы выбрали (a * b + c * d + e), было бы очень сложно найти оптимальные решения просто из-за большого пространства поиска возможностей. Вы можете разделить число, но это означает, что "+ e" усложняет ситуацию, так как вам нужно разложить не только это число, но и несколько сразу же под ним.

Два метода сжатия spring сразу на ум, оба из которых дают вам гораздо лучшее, чем 10% сохранение в пространстве из числового представления.

64-разрядное число варьируется от (без знака):

                         0 to
18,446,744,073,709,551,616

или (подписанный):

-9,223,372,036,854,775,808 to
 9,223,372,036,854,775,807

В обоих случаях вам нужно уменьшить 20 символов (без запятых) на что-то меньшее.

Во-первых, просто BCD-ify номер, который кодирует base64 (фактически немного модифицированное base64, поскольку "/" не будет кошерным в URL-адресе - вы должны использовать один из допустимых символов, например "_").

Преобразование его в BCD будет хранить две цифры (или знак и цифру) в один байт, что дает вам немедленное сокращение пространства на 50% (10 байт). Кодирование его базы 64 (которая превращает каждые 3 байта в 4 символа base64) превратит первые 9 байтов в 12 символов, а этот десятый байт в 2 символа, в общей сложности 14 символов, - 30% экономии.

Единственный лучший метод - просто base64 кодировать двоичное представление. Это лучше, потому что BCD имеет небольшое количество потерь (каждая цифра требует всего 3,32 бит для хранения [log ₂ 10], но BCD использует 4).

Работая над двоичным представлением, нам нужно всего лишь base64 кодировать 64-разрядное число (8 байтов). Это необходимо 8 символов для первых 6 байтов и 3 символа для последних 2 байтов. Это 11 символов base64 для экономии 45%.

Если вам требуется максимальное сжатие, для кодировки URL доступно 73 символа:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
0123456789$-_.+!*'(),

так что технически вы, вероятно, могли бы кодировать базу-73, которая по приблизительным подсчетам будет по-прежнему занимать до 11 символов, но с более сложным кодом, который не стоит на мой взгляд.

Конечно, максимальное сжатие из-за максимальных значений. На другом конце шкалы (1-значный) это кодирование фактически приводит к большему количеству данных (скорее, чем к сжатию). Вы можете видеть, что улучшения начинаются только для чисел более 999, где 4 цифры могут быть превращены в 3 символа base64:

Range (bytes)  Chars  Base64 chars  Compression ratio
-------------  -----  ------------  -----------------
     < 10 (1)      1       2             -100%
    < 100 (1)      2       2                0%
   < 1000 (2)      3       3                0%
   < 10^4 (2)      4       3               25%
   < 10^5 (3)      5       4               20%
   < 10^6 (3)      6       4               33%
   < 10^7 (3)      7       4               42%
   < 10^8 (4)      8       6               25%
   < 10^9 (4)      9       6               33%
  < 10^10 (5)     10       7               30%
  < 10^11 (5)     11       7               36%
  < 10^12 (5)     12       7               41%
  < 10^13 (6)     13       8               38%
  < 10^14 (6)     14       8               42%
  < 10^15 (7)     15      10               33%
  < 10^16 (7)     16      10               37%
  < 10^17 (8)     17      11               35%
  < 10^18 (8)     18      11               38%
  < 10^19 (8)     19      11               42%
  <  2^64 (8)     20      11               45%

Ответ 9

Вы женаты на использовании Java? Python имеет целый пакет, предназначенный именно для этой цели. Он даже очистит кодировку, чтобы вы были безопасными для URL.

Реальное решение Python

Стандартным модулем, который я рекомендую, является base64, который преобразует произвольные укусы символов в дезинфицированный формат base64. Вы можете использовать его в сочетании с модулем pickle, который обрабатывает преобразование из списков длин (фактически произвольного размера) в сжатое строковое представление.

Следующий код должен работать на любой ванильной установке Python:

import base64
import pickle

# get some long list of numbers
a = (854183415,1270335149,228790978,1610119503,1785730631,2084495271,
    1180819741,1200564070,1594464081,1312769708,491733762,243961400,
    655643948,1950847733,492757139,1373886707,336679529,591953597,
    2007045617,1653638786)

# this gets you the url-safe string
str64 = base64.urlsafe_b64encode(pickle.dumps(a,-1))
print str64
>>> gAIoSvfN6TJKrca3S0rCEqMNSk95-F9KRxZwakqn3z58Sh3hYUZKZiePR0pRlwlfSqxGP05KAkNPHUo4jooOSixVFCdK9ZJHdEqT4F4dSvPY41FKaVIRFEq9fkgjSvEVoXdKgoaQYnRxAC4=

# this unwinds it
a64 = pickle.loads(base64.urlsafe_b64decode(str64))
print a64
>>> (854183415, 1270335149, 228790978, 1610119503, 1785730631, 2084495271, 1180819741, 1200564070, 1594464081, 1312769708, 491733762, 243961400, 655643948, 1950847733, 492757139, 1373886707, 336679529, 591953597, 2007045617, 1653638786)

Надеюсь, что это поможет. Использование Python, вероятно, ближе всего к 1-строчному решению.

Ответ 10

Введите исходный запрос алгоритма: существует ли ограничение на размер последнего номера (кроме того, что он должен быть сохранен в 32b int)? (Исходный запрос - это все, что я могу разрешить lol.)

Тот, который производит самый короткий список:

bool negative=(n<1)?true:false;
int j=n%y;
if(n==0 || n==1)
{
list.append(n);
return;
}
while((long64)(n-j*y)>MAX_INT && y>1) //R has to be stored in int32
{
y--;
j=n%y;
}
if(y<=1)
fail //Number has no suitable candidate factors. This shouldn't happen

int i=0;
for(;i<j;i++)
{
list.append(y);
}
list.append(n-y*j);
if(negative)
list[0]*=-1;
return;

Немного упрощен по сравнению с большинством ответов, которые даны до сих пор, но он достигает желаемой функциональности исходного сообщения... Это немного грязно, но, надеюсь, полезно:)

Ответ 11

Не этот модуль?

Пусть / - целочисленное деление (целые числа) и % по модулю.

int result[3];

result[0] = y;
result[1] = x / y;
result[2] = x % y;

Ответ 12

Как и в моем комментарии выше, я не уверен, что я точно понимаю этот вопрос. Но предполагая, что целые числа (n и заданные y), это должно работать для заявленных вами случаев:

multipliers[0] = n / y;
multipliers[1] = y;
addedNumber = n % y;

Ответ 13

Просто установите x: = x/n, где n - наибольшее число, меньшее, чем x и y. Когда вы закончите с x <= y, это ваше последнее число в последовательности.