conversão base numérica como um fluxo de operação

votos
7

Existe uma maneira no espaço de trabalho constante para fazer o tamanho arbitrário e conversões de base arbitrários. Isto é, para converter uma sequência de nnúmeros na gama [1,m]de uma sequência de ceiling(n*log(m)/log(p))números na gama [1,p]usando um mapeamento um-para-um, que ( de preferência, mas não necessariamente) preservadores ordem lexigraphical e dá resultados sequenciais?

Estou particularmente interessado em soluções que sejam viáveis ​​em função da tubulação, ei são capazes de lidar com conjunto de dados maior do que pode ser armazenado na memória RAM.

Eu descobri uma série de soluções que exigem espaço de trabalho proporcional ao tamanho da entrada, mas nenhuma ainda que pode ir longe com constante espaço de trabalho.


Não deixar cair a restrição sequencial fazer alguma diferença? Isto é: permitir entradas lexicographically seqüenciais para resultar em saídas não lexicographically sequenciais:

F(1,2,6,4,3,7,8) -> (5,6,3,2,1,3,5,2,4,3)
F(1,2,6,4,3,7,9) -> (5,6,3,2,1,3,5,2,4,5)

alguns pensamentos:

pode este trabalho?

StreamBase n -> converter ( n, lcm(n,p)) -> convert ( lcm(n,p), p) -> StreamBase p

(onde lcmé menos comum múltipla)

Publicado 19/05/2009 em 20:23
fonte usuário
Em outras línguas...                            


3 respostas

votos
6

Eu não acho que é possível, no caso geral. Se mé uma potência de p(ou vice-versa), ou se ambos são poderes de uma base comum, você pode fazê-lo, uma vez que cada grupo de log m( p) é então independente. No entanto, no caso geral, suponha que você está convertendo o número . O número de equivalentes da base éa1 a2 a3 ... anp

sum(ai * mi-1para iem1..n)

Se nós processados os primeiros idígitos, então nós temos a isoma parcial th. Para calcular a i+1soma 'th parcial, precisamos adicionar . No caso geral, este número vai ter dígitos diferentes de zero na maioria dos lugares, por isso vamos precisar modificar todos os dígitos que já processados até agora. Em outras palavras, nós vamos ter que processar todos os dígitos de entrada antes vamos saber o que os dígitos de saída final será.ai+1 * mi

No caso especial em que msão ambos poderes de uma base comum, ou equivalentemente, se log m( p) é um número racional, então miterá apenas alguns dígitos diferentes de zero em base de pperto da frente, para que possamos saída com segurança a maioria dos dígitos que 've computada até o momento.

Respondeu 19/05/2009 em 20:42
fonte usuário

votos
2

Eu acho que há uma maneira de fazer a conversão raiz de uma forma orientada para o fluxo em ordem lexicográfica. No entanto, o que eu vim acima com não é suficiente para realmente fazê-lo, e ele tem um par de hipóteses:

  1. O comprimento dos números de posicionamento são já conhecidos.
  2. Os números descritos são números inteiros. Eu não tenha considerado o que acontece com a matemática e índices -ive.

Nós temos uma sequência de valores de um de comprimento P , em que cada valor é no intervalo [0, m -1]. Queremos uma sequência de valores de b de comprimento q no intervalo [0, n -1]. Nós podemos trabalhar fora do k th dígitos da nossa seqüência de saída b de um como se segue:

b k = andar [soma (a i * m i para i em 0 a p-1) / N k ] mod n

Deixa reorganizar que soma em duas partes, dividindo-o em um ponto arbitrário z

b k = andar [(soma (a i * m i para i em Z a p-1) + soma (a i * m i para i em 0 a z-1)) / N k ] mod n

Suponha que nós ainda não sabemos os valores de uma entre [0, z-1] e não pode calcular o segundo termo soma. Ficamos com ter que lidar com intervalos. Mas isso ainda nos dá informações sobre b k .

O valor mínimo b k pode ser o seguinte:

b k > = andar [soma (a i * m i para i em Z a p-1) / N k ] mod n

e o valor máximo b k pode ser o seguinte:

b k <= andar [(soma (a i * m i para i em Z a p-1) + m z - 1) / N k ] mod n

Devemos ser capazes de fazer um processo como este:

  1. Inicializar z para ser p . Vamos contar de p que recebermos cada personagem de um .
  2. Inicializar k para o índice do valor mais significativo em b . Se o meu cérebro está ainda a trabalhar, ceil [log n (m p )].
  3. Ler um valor de um . Decremento z .
  4. Calcula-se o valor máximo min e para b k .
  5. Se o MIN e MAX são a mesma, saída b k , e decremento k. Goto 4. (Pode ser possível que já temos valores suficientes para vários valores consecutivos de b k )
  6. Se z ! = 0, em seguida, esperamos mais valores de uma . Goto 3.
  7. Esperemos que, neste momento estamos a fazer.

Eu não tenha considerado como calcular de forma eficiente os valores do intervalo ainda, mas estou razoavelmente confiante de que calcular a soma dos caracteres de entrada de um pode ser feito muito mais razoável do que armazenar todos um . Sem fazer a matemática, porém, eu não vou fazer quaisquer reclamações duras sobre ele embora!

Respondeu 20/05/2009 em 05:19
fonte usuário

votos
0

Sim, é possível

Para cada personagem (s) I você lê, você vai escrever o personagem O (s) com base no teto (log Comprimento * (In) / log (Out)).

Alocar espaço suficiente

Set x to 1
Loop over digits from end to beginning # Horner's method
    Set a to x * digit
    Set t to O - 1
    Loop while a > 0 and t >= 0
        Set a to a + out digit
        Set out digit at position t to a mod to base
    Set a to a / to base
Set x to x * from base
Return converted digit(s)

Assim, por base 16 para 2 (que é fácil), usando "192FE", lemos '1' e convertê-lo, em seguida, repita a '9', então '2' e assim por diante dando-nos '0001', '1001', '0010', '1111' e '1110'. Note que para bases que não são poderes comuns, como base de 17 a Base 2 significaria lendo 1 caracteres e escrever 5.

Respondeu 24/05/2017 em 02:57
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more